lockdep: Implement crossrelease feature

Currently, x86 implementation of save_stack_trace() is walking all stack region word by word regardless of what the trace->max_entries is. However, it's unnecessary to walk after already fulfilling caller's requirement, say, if trace->nr_entries >= trace->max_entries is true.

I measured its overhead and printed its difference of sched_clock() with my QEMU x86 machine. The latency was improved over 70% when trace->max_entries = 5.

Quoted 8 lines · Byungchul Park

Currently, x86 implementation of save_stack_trace() is walking all stack region word by word regardless of what the trace->max_entries is. However, it's unnecessary to walk after already fulfilling caller's requirement, say, if trace->nr_entries >= trace->max_entries is true.

I measured its overhead and printed its difference of sched_clock() with my QEMU x86 machine. The latency was improved over 70% when trace->max_entries = 5.

This code will (probably) be obsoleted soon with my new unwinder.

Also, my previous comment was ignored:

Instead of adding a new callback, why not just check the ops->address() return value? It already returns an error if the array is full.

I think that would be cleaner and would help prevent more callback sprawl.

--
Josh

In non-oops case, it's usually not necessary to check all words of stack area to extract backtrace. Instead, we can achieve it by tracking frame pointer. So made it possible to save stack trace lightly in normal case.

I measured its ovehead and printed its difference of sched_clock() with my QEMU x86 machine. The latency was improved over 80% when trace->max_entries = 5.

kernel/locking/lockdep.c +10 -0

@@ -2215,6 +2178,75 @@ cache_hit:
        return 1;
 }
 
+/*
+ * Look up a dependency chain.
+ */
+static inline struct lock_chain *lookup_chain_cache(u64 chain_key)
+{
+       struct hlist_head *hash_head = chainhashentry(chain_key);
+       struct lock_chain *chain;
+
+       /*
+        * We can walk it lock-free, because entries only get added

Quoted 19 lines · Byungchul Park

kernel/locking/lockdep.c +15 -0

@@ -2215,6 +2178,75 @@ cache_hit:
        return 1;
 }
 
+/*
+ * Look up a dependency chain.
+ */
+static inline struct lock_chain *lookup_chain_cache(u64 chain_key)
+{
+       struct hlist_head *hash_head = chainhashentry(chain_key);
+       struct lock_chain *chain;
+
+       /*
+        * We can walk it lock-free, because entries only get added
+        * to the hash:
+        */
+       hlist_for_each_entry_rcu(chain, hash_head, entry) {
+               if (chain->chain_key == chain_key) {
+                       debug_atomic_inc(chain_lookup_hits);

kernel/locking/lockdep.c cache_hit: · line 2200

Quoted 5 lines

kernel/locking/lockdep.c +5 -0

+                       return chain;
+               }
+       }
+       return NULL;
+}

Byungchul, do you think we should increment chain_lookup_misses before returning NULL from the above function?

--
Nilay

Quoted 20 lines · Nilay Vaish

Quoted 19 lines · Byungchul Park

kernel/locking/lockdep.c +15 -0

@@ -2215,6 +2178,75 @@ cache_hit:
        return 1;
 }
 
+/*
+ * Look up a dependency chain.
+ */
+static inline struct lock_chain *lookup_chain_cache(u64 chain_key)
+{
+       struct hlist_head *hash_head = chainhashentry(chain_key);
+       struct lock_chain *chain;
+
+       /*
+        * We can walk it lock-free, because entries only get added
+        * to the hash:
+        */
+       hlist_for_each_entry_rcu(chain, hash_head, entry) {
+               if (chain->chain_key == chain_key) {
+                       debug_atomic_inc(chain_lookup_hits);

Quoted 8 lines

kernel/locking/lockdep.c cache_hit: · line 2200

Quoted 5 lines

kernel/locking/lockdep.c +5 -0

+                       return chain;
+               }
+       }
+       return NULL;
+}

Byungchul, do you think we should increment chain_lookup_misses before returning NULL from the above function?

Hello,

No, I don't think so.
It will be done in add_chain_cache().

Quoted 32 lines · Byungchul Park

Quoted 20 lines · Nilay Vaish

Quoted 19 lines · Byungchul Park

kernel/locking/lockdep.c +15 -0

@@ -2215,6 +2178,75 @@ cache_hit:
        return 1;
 }
 
+/*
+ * Look up a dependency chain.
+ */
+static inline struct lock_chain *lookup_chain_cache(u64 chain_key)
+{
+       struct hlist_head *hash_head = chainhashentry(chain_key);
+       struct lock_chain *chain;
+
+       /*
+        * We can walk it lock-free, because entries only get added
+        * to the hash:
+        */
+       hlist_for_each_entry_rcu(chain, hash_head, entry) {
+               if (chain->chain_key == chain_key) {
+                       debug_atomic_inc(chain_lookup_hits);

Quoted 8 lines

kernel/locking/lockdep.c cache_hit: · line 2200

Quoted 5 lines

kernel/locking/lockdep.c +5 -0

+                       return chain;
+               }
+       }
+       return NULL;
+}

Byungchul, do you think we should increment chain_lookup_misses before returning NULL from the above function?

Hello,

Quoted 3 lines

No, I don't think so.
It will be done in add_chain_cache().

I think you are assuming that a call to lookup will always be followed by add. I thought the point of breaking the original function into two was that each of the functions can be used individually, without the other being called. This means we would not increment the number

of misses when only lookup() gets called, but not add(). Or we would

increment the number of misses when only add() is called and not lookup().

It really seems odd to me that hits get incremented in lookup and misses don't.

--
Nilay

Crossrelease feature calls a lock 'crosslock' if it is releasable in any context. For crosslock, all locks having been held in the release context of the crosslock, until eventually the crosslock will be released, have dependency with the crosslock.

Using crossrelease feature, we can detect deadlock possibility even for lock_page(), wait_for_complete() and so on.

Quoted 8 lines · Byungchul Park

Crossrelease feature calls a lock 'crosslock' if it is releasable in any context. For crosslock, all locks having been held in the release context of the crosslock, until eventually the crosslock will be released, have dependency with the crosslock.

Using crossrelease feature, we can detect deadlock possibility even for lock_page(), wait_for_complete() and so on.

Completely inadequate.

Please explain how cross-release does what it does. Talk about lock graphs and such.

I do not have time to reverse engineer this stuff.

Quoted 5 lines · Byungchul Park

Crossrelease feature calls a lock 'crosslock' if it is releasable in any context. For crosslock, all locks having been held in the release context of the crosslock, until eventually the crosslock will be released, have dependency with the crosslock.

Quoted 3 lines

Using crossrelease feature, we can detect deadlock possibility even for lock_page(), wait_for_complete() and so on.

Completely inadequate.

Please explain how cross-release does what it does. Talk about lock graphs and such.

I do not have time to reverse engineer this stuff.

So the idea is to add support for non-owner serialization primitives, like completions/semaphores, and so far I've not looked at the code yet. I did spend 2+ hours trying to decipher your documentation thing, but am still confused, that thing is exceedingly hard to parse/read.

So the typical scenario would be something like:

L a L a
U a
W b C b

where L := lock, U := unlock, W := wait_for_completion and C := complete.

On the left, the blocking thread we can easily observe the 'b depends on a' relation, since we block while holding a.

On the right however that same relation is hard to see, since by the

time we would run complete, a has already been released.

I _think_ you propose to keep track of all prior held locks and then use the union of the held list on the block-chain with the prior held list from the complete context.

The document describes you have a prior held list, and that its a circular thing, but it then completely fails to specify what gets added and how its used.

Also, by it being a circular list (of indeterminate, but finite size), there is the possibility of missing dependencies if they got spooled out by recent activity.

The document has an example in the section 'How cross release works' (the 3rd) that simply cannot be. It lists lock action _after_ acquire,

but you place the acquire in wait_for_completion. We _block_ there.

Is this the general idea?

If so, I cannot see how something like:

W a W b
C b C a

would work, somewhere in that document it states that this would be handled by the existing dependencies, but I cannot see how. The blocking

thread (either one) has no held context, therefore the previously mentioned union of held and prev-held is empty.

The alternative is not doing the union, but then you end up with endless pointless dependencies afaict.

On the whole 'release context' thing you want to cast lockdep in, please consider something like:

L a     L b
L b     L a
U a     U a
U b     U b

Note that the release order of locks is immaterial and can generate 'wrong' dependencies. Note how on both sides a is released under b,

failing to observe the stil obvious AB-BA deadlock.

Note that lockdep doesn't model release or anything, it models blocked-on relations, like PI does.

Quoted 16 lines · Peter Zijlstra

So the idea is to add support for non-owner serialization primitives, like completions/semaphores, and so far I've not looked at the code yet. I did spend 2+ hours trying to decipher your documentation thing, but am still confused, that thing is exceedingly hard to parse/read.

So the typical scenario would be something like:

L a L a
U a
W b C b

where L := lock, U := unlock, W := wait_for_completion and C := complete.

Quoted 2 lines

On the left, the blocking thread we can easily observe the 'b depends on a' relation, since we block while holding a.

I think 'a depends on b' relation.

Why does b depend on a? b depends on a's what?

Quoted 1 line

On the right however that same relation is hard to see, since by the

Yes, there's no dependency on the right side of your example.

Quoted 1 line

time we would run complete, a has already been released.

I will change your example a little bit.

W b
~~~~~~~ <- serialized
L a
U a
C b

(Remind crossrelease considers dependencies in only case that lock sequence serialized is observable.)

There's a dependency in this case, like 'b depends on a' relation. 'C b' may not be hit, depending on the result of 'L a', that is, acquired or not.

Quoted 3 lines

I _think_ you propose to keep track of all prior held locks and then use the union of the held list on the block-chain with the prior held list from the complete context.

Almost right. Only thing we need to do to consider the union is to connect two chains of two contexts by adding one dependency 'b -> a'.

Quoted 3 lines

The document describes you have a prior held list, and that its a circular thing, but it then completely fails to specify what gets added and how its used.

Why does it fail? It keeps them in the form of hlock. This data is enough to generate dependencies.

Quoted 3 lines

Also, by it being a circular list (of indeterminate, but finite size), there is the possibility of missing dependencies if they got spooled out by recent activity.

Yes, right. They might be missed. It means just missing some chances to check a deadlock. It's all. Better than do nothing.

Quoted 2 lines

The document has an example in the section 'How cross release works' (the 3rd) that simply cannot be. It lists lock action _after_ acquire,

Could you tell me more? Why cannot it be?

Quoted 4 lines

but you place the acquire in wait_for_completion. We _block_ there.

Is this the general idea?

Quoted 4 lines

If so, I cannot see how something like:

W a W b
C b C a

I didn't tell it works in this case. But it can be a future work. I'm not sure but I don't think making it work is impossible at all. But anyway current implementation cannot deal with this case.

Quoted 8 lines

On the whole 'release context' thing you want to cast lockdep in, please consider something like:

L a     L b
L b     L a
U a     U a
U b     U b

Quoted 2 lines

Note that the release order of locks is immaterial and can generate 'wrong' dependencies. Note how on both sides a is released under b,

Who said the release order is important? Wrong for what?

Quoted 6 lines

Quoted 3 lines

I _think_ you propose to keep track of all prior held locks and then use the union of the held list on the block-chain with the prior held list from the complete context.

Almost right. Only thing we need to do to consider the union is to connect two chains of two contexts by adding one dependency 'b -> a'.

Sure, but how do you arrive at which connection to make. The document is entirely silent on this crucial point.

The union between the held-locks of the blocked and prev-held-locks of the release should give a fair indication I think, but then, I've not thought too hard on this yet.

Quoted 10 lines · Peter Zijlstra

Quoted 6 lines

Quoted 3 lines

I _think_ you propose to keep track of all prior held locks and then use the union of the held list on the block-chain with the prior held list from the complete context.

Almost right. Only thing we need to do to consider the union is to connect two chains of two contexts by adding one dependency 'b -> a'.

Sure, but how do you arrive at which connection to make. The document is entirely silent on this crucial point.

Quoted 3 lines

The union between the held-locks of the blocked and prev-held-locks of the release should give a fair indication I think, but then, I've not thought too hard on this yet.

s/union/intersection/

those that are in both sets.

Quoted 20 lines · Byungchul Park

Quoted 18 lines · Peter Zijlstra

So the idea is to add support for non-owner serialization primitives, like completions/semaphores, and so far I've not looked at the code yet. I did spend 2+ hours trying to decipher your documentation thing, but am still confused, that thing is exceedingly hard to parse/read.

So the typical scenario would be something like:

L a L a
U a
W b C b

where L := lock, U := unlock, W := wait_for_completion and C := complete.

On the left, the blocking thread we can easily observe the 'b depends on a' relation, since we block while holding a.

Quoted 3 lines

I think 'a depends on b' relation.

Why does b depend on a? b depends on a's what?

b blocks while holding a. In any case, for the graph it doesn't matter, its not a directed graph as such, all we care about is acyclic.

Quoted 3 lines

Quoted 1 line

On the right however that same relation is hard to see, since by the

Yes, there's no dependency on the right side of your example.

Well, there is, its just not trivially observable. We must be able to acquire a in order to complete b, therefore there is a dependency.

Quoted 10 lines

Quoted 1 line

time we would run complete, a has already been released.

I will change your example a little bit.

W b
~~~~~~~ <- serialized
L a
U a
C b

Quoted 2 lines

(Remind crossrelease considers dependencies in only case that lock sequence serialized is observable.)

What does that mean? Any why? This is a random point in time without actual meaning.

Quoted 3 lines

There's a dependency in this case, like 'b depends on a' relation. 'C b' may not be hit, depending on the result of 'L a', that is, acquired or not.

With or without a random reference point, the dependency is there.

Quoted 6 lines

Quoted 3 lines

I _think_ you propose to keep track of all prior held locks and then use the union of the held list on the block-chain with the prior held list from the complete context.

Almost right. Only thing we need to do to consider the union is to connect two chains of two contexts by adding one dependency 'b -> a'.

Sure, but how do you arrive at which connection to make. The document is entirely silent on this crucial point.

The union between the held-locks of the blocked and prev-held-locks of the release should give a fair indication I think, but then, I've not thought too hard on this yet.

Quoted 6 lines

Quoted 3 lines

The document describes you have a prior held list, and that its a circular thing, but it then completely fails to specify what gets added and how its used.

Why does it fail? It keeps them in the form of hlock. This data is enough to generate dependencies.

It fails to explain. It just barely mentions you keep them, it doesn't mention how they're used or why.

Quoted 6 lines

Quoted 3 lines

Also, by it being a circular list (of indeterminate, but finite size), there is the possibility of missing dependencies if they got spooled out by recent activity.

Yes, right. They might be missed. It means just missing some chances to check a deadlock. It's all. Better than do nothing.

Sure, but you didn't specify. Again, the document is very ambiguous and ill specified.

Quoted 5 lines

Quoted 3 lines

The document has an example in the section 'How cross release works' (the 3rd) that simply cannot be. It lists lock action _after_ acquire,

Could you tell me more? Why cannot it be?

Once you block you cannot take more locks, that simply doesnt make sense.

Quoted 4 lines

Quoted 4 lines

but you place the acquire in wait_for_completion. We _block_ there.

Is this the general idea?

Quoted 8 lines

Quoted 4 lines

If so, I cannot see how something like:

W a W b
C b C a

I didn't tell it works in this case. But it can be a future work. I'm not sure but I don't think making it work is impossible at all. But anyway current implementation cannot deal with this case.

+4. 'crosslock a -> crosslock b' dependency

(quoted diff) +3 -0

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

Says something different, doesn't it?

Quoted 8 lines

Quoted 8 lines

On the whole 'release context' thing you want to cast lockdep in, please consider something like:

L a     L b
L b     L a
U a     U a
U b     U b

Quoted 4 lines

Quoted 2 lines

Note that the release order of locks is immaterial and can generate 'wrong' dependencies. Note how on both sides a is released under b,

Who said the release order is important? Wrong for what?

Well, again, you mention 'release context' without actually specifying what you mean with that.

L a
L b
U b

and

L a
L b
U a

Here the unlocks obviously have different context. Without further specification its simply impossible to tell what you mean.

Quoted 21 lines · Peter Zijlstra

Quoted 20 lines · Byungchul Park

Quoted 18 lines · Peter Zijlstra

So the idea is to add support for non-owner serialization primitives, like completions/semaphores, and so far I've not looked at the code yet. I did spend 2+ hours trying to decipher your documentation thing, but am still confused, that thing is exceedingly hard to parse/read.

So the typical scenario would be something like:

L a L a
U a
W b C b

where L := lock, U := unlock, W := wait_for_completion and C := complete.

On the left, the blocking thread we can easily observe the 'b depends on a' relation, since we block while holding a.

Quoted 6 lines

Quoted 3 lines

I think 'a depends on b' relation.

Why does b depend on a? b depends on a's what?

b blocks while holding a. In any case, for the graph it doesn't matter, its not a directed graph as such, all we care about is acyclic.

It's a directed graph.The meaning of backward traverse is different from the meaning of forward traverse, isn't it?

Quoted 6 lines

Quoted 3 lines

Quoted 1 line

On the right however that same relation is hard to see, since by the

Yes, there's no dependency on the right side of your example.

Well, there is, its just not trivially observable. We must be able to acquire a in order to complete b, therefore there is a dependency.

No. We cannot say there is a dependency unconditionally. There can be a dependency or not.

L a L a
U a
~~~~~~~~~ what if serialized by something?
W b C b

If something we don't recognize serializes locks, which ensures 'W b' happens after 'L a , U a' in the other context, then there's no dependency here.

We should say 'b depends on a' in only case that the sequence 'W b and then L a and then C b, where last two ops are in same context' _actually_ happened at least once. Otherwise, it might add a false dependency.

It's same as how original lockdep works with typical locks. It adds a dependency only when a lock is actually hit.

Quoted 10 lines

Quoted 10 lines

Quoted 1 line

time we would run complete, a has already been released.

I will change your example a little bit.

W b
~~~~~~~ <- serialized
L a
U a
C b

Quoted 5 lines

Quoted 2 lines

(Remind crossrelease considers dependencies in only case that lock sequence serialized is observable.)

What does that mean? Any why? This is a random point in time without actual meaning.

It's not random point. We have to consider meaningful sequences among those which are globally observable. That's why we need to serialize those locks. For example,

W b
L a
U a
C b

Once this sequence is observable globally, we can say 'It's possible to run in this sequence. Is this sequence problematic or not?'.

L a
U a
W b
C b

If only this sequence can be observable, we should not assume this sequence can be changed. However once the former sequence happens, it has a possibility to hit the same sequence again later. So we can check deadlock possibility with the sequence,

_not randomly_.

Quoted 5 lines

Quoted 3 lines

There's a dependency in this case, like 'b depends on a' relation. 'C b' may not be hit, depending on the result of 'L a', that is, acquired or not.

With or without a random reference point, the dependency is there.

The dependency might not be there.

Quoted 9 lines

Quoted 6 lines

Quoted 3 lines

I _think_ you propose to keep track of all prior held locks and then use the union of the held list on the block-chain with the prior held list from the complete context.

Almost right. Only thing we need to do to consider the union is to connect two chains of two contexts by adding one dependency 'b -> a'.

Sure, but how do you arrive at which connection to make. The document is entirely silent on this crucial point.

We need to connect between the crosslock and the first lock among locks having been acquired since the crosslock was held. Others will be connected each other by original lockdep.

By the way, does my document miss this description? If so, sorry. I will check and update it.

Quoted 3 lines

The union between the held-locks of the blocked and prev-held-locks of the release should give a fair indication I think, but then, I've not thought too hard on this yet.

I make the union only If actually the lock sequence happened once so that it's globally visible.

Quoted 9 lines

Quoted 6 lines

Quoted 3 lines

The document describes you have a prior held list, and that its a circular thing, but it then completely fails to specify what gets added and how its used.

Why does it fail? It keeps them in the form of hlock. This data is enough to generate dependencies.

It fails to explain. It just barely mentions you keep them, it doesn't mention how they're used or why.

Okay. I need to explain more about that.

Quoted 9 lines

Quoted 6 lines

Quoted 3 lines

Also, by it being a circular list (of indeterminate, but finite size), there is the possibility of missing dependencies if they got spooled out by recent activity.

Yes, right. They might be missed. It means just missing some chances to check a deadlock. It's all. Better than do nothing.

Sure, but you didn't specify. Again, the document is very ambiguous and ill specified.

Yes, I need to supplement the latter half as you said. I will do it.

Quoted 6 lines

Quoted 5 lines

Quoted 3 lines

The document has an example in the section 'How cross release works' (the 3rd) that simply cannot be. It lists lock action _after_ acquire,

Could you tell me more? Why cannot it be?

Quoted 2 lines

Once you block you cannot take more locks, that simply doesnt make sense.

No. Peter.. lockdep check possibilities. All lockdep operations are performed assuming this same sequence can happen again later but in a little bit different order between more than two contexts so that actual deadlock can happen then.

No doubt, it cannot take more locks while blocked at the time. But it's not important for lockdep to work.

Quoted 18 lines

Quoted 4 lines

Quoted 4 lines

but you place the acquire in wait_for_completion. We _block_ there.

Is this the general idea?

Quoted 8 lines

Quoted 4 lines

If so, I cannot see how something like:

W a W b
C b C a

I didn't tell it works in this case. But it can be a future work. I'm not sure but I don't think making it work is impossible at all. But anyway current implementation cannot deal with this case.

+4. 'crosslock a -> crosslock b' dependency

(quoted diff) +3 -0

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

Quoted 1 line

Says something different, doesn't it?

Really sorry. I made you much confused. I will update it.

Quoted 20 lines

Quoted 8 lines

Quoted 8 lines

On the whole 'release context' thing you want to cast lockdep in, please consider something like:

L a     L b
L b     L a
U a     U a
U b     U b

Quoted 4 lines

Quoted 2 lines

Note that the release order of locks is immaterial and can generate 'wrong' dependencies. Note how on both sides a is released under b,

Who said the release order is important? Wrong for what?

Well, again, you mention 'release context' without actually specifying what you mean with that.

L a
L b
U b

Quoted 8 lines

and

L a
L b
U a

Here the unlocks obviously have different context. Without further specification its simply impossible to tell what you mean.

I mentioned what the release context means in the document. Or I don't understand what you are asking now.

--
Thanks,
Byungchul

Quoted 2 lines

Well, there is, its just not trivially observable. We must be able to acquire a in order to complete b, therefore there is a dependency.

No. We cannot say there is a dependency unconditionally. There can be a dependency or not.

L a L a
U a
~~~~~~~~~ what if serialized by something?

W b C b

If something we don't recognize serializes locks, which ensures 'W b' happens after 'L a , U a' in the other context, then there's no dependency here.

We should say 'b depends on a' in only case that the sequence 'W b and then L a and then C b, where last two ops are in same context' _actually_ happened at least once. Otherwise, it might add a false dependency.

It's same as how original lockdep works with typical locks. It adds a dependency only when a lock is actually hit.

Quoted 2 lines

What does that mean? Any why? This is a random point in time without actual meaning.

It's not random point. We have to consider meaningful sequences among those which are globally observable. That's why we need to serialize those locks.

For example,

W b
L a
U a
C b

Once this sequence is observable globally, we can say 'It's possible to run in this sequence. Is this sequence problematic or not?'.

L a
U a
W b
C b

If only this sequence can be observable, we should not assume this sequence can be changed. However once the former sequence happens, it has a possibility to hit the same sequence again later. So we can check deadlock possibility with the sequence,

_not randomly_.

We need to connect between the crosslock and the first lock among locks having been acquired since the crosslock was held.

Others will be
connected each other by original lockdep.

By the way, does my document miss this description? If so, sorry. I will check and update it.

Quoted 3 lines · Byungchul Park

Quoted 2 lines

Well, there is, its just not trivially observable. We must be able to acquire a in order to complete b, therefore there is a dependency.

Quoted 6 lines

No. We cannot say there is a dependency unconditionally. There can be a dependency or not.

L a L a
U a
~~~~~~~~~ what if serialized by something?

Well, there's no serialization in the example, so no what if.

Quoted 5 lines

W b C b

If something we don't recognize serializes locks, which ensures 'W b' happens after 'L a , U a' in the other context, then there's no dependency here.

Its not there.

Quoted 7 lines

We should say 'b depends on a' in only case that the sequence 'W b and then L a and then C b, where last two ops are in same context' _actually_ happened at least once. Otherwise, it might add a false dependency.

It's same as how original lockdep works with typical locks. It adds a dependency only when a lock is actually hit.

But since these threads are independently scheduled there is no point in transferring the point in time thread A does W to thread B. There is no relation there.

B could have already executed the complete or it could not yet have started execution at all or anything in between, entirely random.

Quoted 6 lines

Quoted 2 lines

What does that mean? Any why? This is a random point in time without actual meaning.

It's not random point. We have to consider meaningful sequences among those which are globally observable. That's why we need to serialize those locks.

Serialize how? there is no serialization.

Quoted 16 lines

For example,

W b
L a
U a
C b

Once this sequence is observable globally, we can say 'It's possible to run in this sequence. Is this sequence problematic or not?'.

L a
U a
W b
C b

Quoted 6 lines

If only this sequence can be observable, we should not assume this sequence can be changed. However once the former sequence happens, it has a possibility to hit the same sequence again later. So we can check deadlock possibility with the sequence,

_not randomly_.

I still don't get it.

Quoted 2 lines

We need to connect between the crosslock and the first lock among locks having been acquired since the crosslock was held.

Which can be _any_ lock in the history of that thread. It could be rq->lock from getting the thread scheduled.

Quoted 6 lines

Others will be
connected each other by original lockdep.

By the way, does my document miss this description? If so, sorry. I will check and update it.

I couldn't find anything useful, but then I could not understand most of what was written, and I tried hard :-(

Quoted 6 lines

But since these threads are independently scheduled there is no point in transferring the point in time thread A does W to thread B. There is no relation there.

B could have already executed the complete or it could not yet have started execution at all or anything in between, entirely random.

Of course B could have already executed the complete or it could not yet have started execution at all or anything in between. But it's not entirely random.

It might be a random point since they are independently scheduled, but it's not entirely random. And it's a random point among valid points which lockdep needs to consider. For example,

CONTEXT 1 CONTEXT 2(forked one)
========= =====================
(a) acquire F
acquire A acquire G
acquire B wait_for_completion Z
acquire C
(b) acquire H
fork 2 acquire I
acquire D acquire J
complete Z acquire K

I can provide countless examples with which I can say you're wrong. In this case, all acquires between (a) and (b) must be ignored when generating dependencies with complete operation of Z.

Quoted 16 lines · Byungchul Park

Quoted 6 lines

But since these threads are independently scheduled there is no point in transferring the point in time thread A does W to thread B. There is no relation there.

B could have already executed the complete or it could not yet have started execution at all or anything in between, entirely random.

Of course B could have already executed the complete or it could not yet have started execution at all or anything in between. But it's not entirely random.

It might be a random point since they are independently scheduled, but it's not entirely random. And it's a random point among valid points which lockdep needs to consider. For example,

Quoted 11 lines

CONTEXT 1 CONTEXT 2(forked one)
========= =====================
(a) acquire F
acquire A acquire G
acquire B wait_for_completion Z
acquire C
(b) acquire H
fork 2 acquire I
acquire D acquire J
complete Z acquire K

I'm hoping you left out the releases for brevity? Because calling fork() with locks held is _really_ poor form.

Quoted 4 lines

I can provide countless examples with which I can say you're wrong. In this case, all acquires between (a) and (b) must be ignored when generating dependencies with complete operation of Z.

I still don't get the point. Why does this matter?

Sure, A-C are irrelevant in this example, but I don't see how they're differently irrelevant from a whole bunch of other prior state action.

Earlier you said the algorithm for selecting the dependency is the first acquire observed in the completing thread after the wait_for_completion(). Is this correct?

				W z

	A a
	for (i<0;i<many;i++) {
	  A x[i]
	  R x[i]
	}
	R a

	<IRQ>
	  A b
	  R b
	  C z
	</IRQ>

That would be 'a' in this case, but that isn't at all related. Its just as irrelevant as your A-C. And we can pick @many as big as needed to flush the prev held cyclic buffer (although I've no idea how that matters either).

What we want here is to link z to b, no? That is the last, not the first

acquire, it also is independent of when W happened.

At the same time, picking the last is no guarantee either, since that can equally miss dependencies. Suppose the IRQ handler did:

	<IRQ>
	  A c
	  R c
	  A b
	  R b
	  C z
	</IRQ>

instead. We'd miss the z depends on c relation, and since they're independent lock sections, lockdep wouldn't make a b-c relation either.

Clearly I'm still missing stuff...

Quoted 30 lines · Peter Zijlstra

Quoted 16 lines · Byungchul Park

Quoted 6 lines

But since these threads are independently scheduled there is no point in transferring the point in time thread A does W to thread B. There is no relation there.

B could have already executed the complete or it could not yet have started execution at all or anything in between, entirely random.

Of course B could have already executed the complete or it could not yet have started execution at all or anything in between. But it's not entirely random.

It might be a random point since they are independently scheduled, but it's not entirely random. And it's a random point among valid points which lockdep needs to consider. For example,

Quoted 11 lines

CONTEXT 1 CONTEXT 2(forked one)
========= =====================
(a) acquire F
acquire A acquire G
acquire B wait_for_completion Z
acquire C
(b) acquire H
fork 2 acquire I
acquire D acquire J
complete Z acquire K

Quoted 2 lines

I'm hoping you left out the releases for brevity? Because calling fork() with locks held is _really_ poor form.

Exactly. Sorry. I shouldn't have omitted releases.

Quoted 7 lines

Quoted 4 lines

I can provide countless examples with which I can say you're wrong. In this case, all acquires between (a) and (b) must be ignored when generating dependencies with complete operation of Z.

I still don't get the point. Why does this matter?

Quoted 7 lines

Sure, A-C are irrelevant in this example, but I don't see how they're differently irrelevant from a whole bunch of other prior state action.

Earlier you said the algorithm for selecting the dependency is the first acquire observed in the completing thread after the wait_for_completion(). Is this correct?

Sorry for insufficient description.

held_locks of left context will be,

time 1: a
time 2: a, x[0]
time 3: a, x[1]
...
time n: b

Between time 1 and time (n-1), 'a' will be the first among held_locks. At time n, 'b' will be the fist among held_locks. So 'a' and 'b' should be connected to 'z' if we ignore IRQ context. (I will explain it soon.)

Acquire x[i] is also valid one but crossrelease doesn't take it into account since original lockdep will cover using 'a -> x[i]'. So only connections we need are 'z -> a' and 'z -> b'.

Quoted 16 lines

				W z

	A a
	for (i<0;i<many;i++) {
	  A x[i]
	  R x[i]
	}
	R a

	<IRQ>
	  A b
	  R b
	  C z
	</IRQ>

My crossrelease implementation distinguishes each IRQ from normal context or other IRQs in different timeline, even though they might share held_locks. So in this example, precisely speaking, there are two different contexts. One is normal context and the other is IRQ context. So only 'A b' is related with 'W z' in this example.

Quoted 5 lines

That would be 'a' in this case, but that isn't at all related. Its just as irrelevant as your A-C. And we can pick @many as big as needed to flush the prev held cyclic buffer (although I've no idea how that matters either).

I designed crossrelease so that x[i] is not added into ring buffer because adding 'z -> a' is sufficient and x[i] doesn't need to be taken into account in this case.

Quoted 2 lines

What we want here is to link z to b, no? That is the last, not the first

Exactly right. Only 'z -> b' must be added under considering IRQ context. That is the first among held_locks in the IRQ context.

Quoted 1 line

acquire, it also is independent of when W happened.

If the IRQ is really random, then it can happen before W z and it can also happen after W z. We cannot determine the time. Then we need to consider all combination and possibility. It's a key point. We have to consider dependencies for all possibility.

However, we don't know what synchronizes the flow. So it must be based on what actually happened, to identify true dependencies.

Quoted 4 lines

At the same time, picking the last is no guarantee either, since that can equally miss dependencies. Suppose the IRQ handler did:

Quoted 8 lines

	<IRQ>
	  A c
	  R c
	  A b
	  R b
	  C z
	</IRQ>

time 1: c (in held_locks)
time 2: b (in held_locks)

So 'c' and 'b' can be the first among held_locks at each moment. So 'z -> b' and 'z -> c' will be added.

Quoted 5 lines

instead. We'd miss the z depends on c relation, and since they're independent lock sections, lockdep wouldn't make a b-c relation either.

Clearly I'm still missing stuff...

Sorry for insufficient description. I tried to describ crossrelease in as much detail as possible, really.

The reason why I consider only the first among valid locks in held_locks is simple. For example,

Context 1
A a -> A b -> A crosslock -> R a -> R b

Context 2
A c -> A d -> R d -> R the crosslock -> R c

If 'A c' after 'A crosslock' is possible, then 'A crosslock' does not only depends on 'A c' but also 'A d'. But all dependencies we need to add is only 'crosslock -> c' because 'crosslock -> d' will be covered by 'crosslock -> c' and 'a -> b'. 'a -> b' is added by original lockdep.

Quoted 30 lines · Peter Zijlstra

Quoted 16 lines · Byungchul Park

Quoted 6 lines

But since these threads are independently scheduled there is no point in transferring the point in time thread A does W to thread B. There is no relation there.

B could have already executed the complete or it could not yet have started execution at all or anything in between, entirely random.

Of course B could have already executed the complete or it could not yet have started execution at all or anything in between. But it's not entirely random.

It might be a random point since they are independently scheduled, but it's not entirely random. And it's a random point among valid points which lockdep needs to consider. For example,

Quoted 11 lines

CONTEXT 1 CONTEXT 2(forked one)
========= =====================
(a) acquire F
acquire A acquire G
acquire B wait_for_completion Z
acquire C
(b) acquire H
fork 2 acquire I
acquire D acquire J
complete Z acquire K

Quoted 2 lines

I'm hoping you left out the releases for brevity? Because calling fork() with locks held is _really_ poor form.

Exactly. Sorry. I shouldn't have omitted releases.

Quoted 7 lines

Quoted 4 lines

I can provide countless examples with which I can say you're wrong. In this case, all acquires between (a) and (b) must be ignored when generating dependencies with complete operation of Z.

I still don't get the point. Why does this matter?

Quoted 7 lines

Sure, A-C are irrelevant in this example, but I don't see how they're differently irrelevant from a whole bunch of other prior state action.

Earlier you said the algorithm for selecting the dependency is the first acquire observed in the completing thread after the wait_for_completion(). Is this correct?

Sorry for insufficient description.

held_locks of left context will be,

time 1: a
time 2: a, x[0]
time 3: a, x[1]
...
time n: b

Between time 1 and time (n-1), 'a' will be the first among held_locks. At time n, 'b' will be the fist among held_locks. So 'a' and 'b' should be connected to 'z' if we ignore IRQ context. (I will explain it soon.)

Acquire x[i] is also valid one but crossrelease doesn't take it into account since original lockdep will cover using 'a -> x[i]'. So only

connections we need are 'z -> a' and 'z -> b'.

Quoted 16 lines

				W z

	A a
	for (i<0;i<many;i++) {
	  A x[i]
	  R x[i]
	}
	R a

	<IRQ>
	  A b
	  R b
	  C z
	</IRQ>

My crossrelease implementation distinguishes each IRQ from normal context or other IRQs in different timeline, even though they might share held_locks. So in this example, precisely speaking, there are two different contexts. One is normal context and the other is IRQ context. So only 'A b' is related with 'W z' in this example.

Quoted 5 lines

That would be 'a' in this case, but that isn't at all related. Its just as irrelevant as your A-C. And we can pick @many as big as needed to flush the prev held cyclic buffer (although I've no idea how that matters either).

I designed crossrelease so that x[i] is not added into ring buffer because adding 'z -> a' is sufficient and x[i] doesn't need to be taken into account in this case.

Quoted 2 lines

What we want here is to link z to b, no? That is the last, not the first

Exactly right. Only 'z -> b' must be added under considering IRQ context. That is the first among held_locks in the IRQ context.

Quoted 1 line

acquire, it also is independent of when W happened.

If the IRQ is really random, then it can happen before W z and it can also happen after W z. We cannot determine the time. Then we need to consider all combination and possibility. It's a key point. We have to consider dependencies for all possibility.

However, we don't know what synchronizes the flow. So it must be based on

what actually happened, to identify true dependencies.

Quoted 4 lines

At the same time, picking the last is no guarantee either, since that can equally miss dependencies. Suppose the IRQ handler did:

Quoted 8 lines

	<IRQ>
	  A c
	  R c
	  A b
	  R b
	  C z
	</IRQ>

time 1: c (in held_locks)
time 2: b (in held_locks)

So 'c' and 'b' can be the first among held_locks at each moment.

So 'z -> b' and 'z -> c' will be added.

Quoted 5 lines

instead. We'd miss the z depends on c relation, and since they're independent lock sections, lockdep wouldn't make a b-c relation either.

Clearly I'm still missing stuff...

Sorry for insufficient description. I tried to describ crossrelease in as much detail as possible, really.

The reason why I consider only the first among valid locks in held_locks is simple. For example,

Context 1
A a -> A b -> A crosslock -> R a -> R b

Context 2
A c -> A d -> R d -> R the crosslock -> R c

If 'A c' after 'A crosslock' is possible, then 'A crosslock' does not only depends on 'A c' but also 'A d'. But all dependencies we need to add is only 'crosslock -> c' because 'crosslock -> d' will be covered by 'crosslock -> c' and 'a -> b'. Here, 'a -> b' is added by original lockdep.

Clearly I'm still missing stuff...

This document describes the concept of crossrelease feature, which generalizes what causes a deadlock and how can detect a deadlock.

Signed-off-by Byungchul Park <[email protected]>

---
 Documentation/locking/crossrelease.txt | 785 +++++++++++++++++++++++++++++++++
 1 file changed, 785 insertions(+)
 create mode 100644 Documentation/locking/crossrelease.txt

Quoted 8 lines · Byungchul Park

This document describes the concept of crossrelease feature, which generalizes what causes a deadlock and how can detect a deadlock.

Signed-off-by Byungchul Park <[email protected]>

---
 Documentation/locking/crossrelease.txt | 785 +++++++++++++++++++++++++++++++++
 1 file changed, 785 insertions(+)
 create mode 100644 Documentation/locking/crossrelease.txt

Byungchul, I mostly skimmed through the document. I suggest that we split this document. The initial 1/4 of the document talks about lockdep's current implementation which I believe should be combined with the file: Documentation/locking/lockdep-design.txt. Tomorrow I would try to understand the document in detail and hopefully provide some useful comments.

--
Nilay

This document describes the concept of crossrelease feature, which generalizes what causes a deadlock and how can detect a deadlock.

Signed-off-by Byungchul Park <[email protected]>

---
 Documentation/locking/crossrelease.txt | 785 +++++++++++++++++++++++++++++++++
 1 file changed, 785 insertions(+)
 create mode 100644 Documentation/locking/crossrelease.txt

Documentation/locking/crossrelease.txt new file +40 -0

new file mode 100644
index 0000000..78558af
@@ -0,0 +1,785 @@
+Crossrelease
+============
+
+Started by Byungchul Park <[email protected]>
+
+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.
+
+
+==========

Documentation/locking/crossrelease.txt new file +16 -0

+
+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

Documentation/locking/crossrelease.txt new file +19 -0

+
+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,

Documentation/locking/crossrelease.txt new file +34 -0

+
+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

Documentation/locking/crossrelease.txt new file +21 -0

+
+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

Documentation/locking/crossrelease.txt new file +11 -0

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

Documentation/locking/crossrelease.txt new file +23 -0

+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

Documentation/locking/crossrelease.txt new file +35 -0

+
+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
+       --------------  --------------

Documentation/locking/crossrelease.txt new file +273 -0

+
+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