| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <1481260331-360-16-git-send-email-byungchul.park@lge.com>
Date: Fri, 9 Dec 2016 14:12:11 +0900
From: Byungchul Park <byungchul.park@....com>
To: peterz@...radead.org, mingo@...nel.org
Cc: tglx@...utronix.de, walken@...gle.com, boqun.feng@...il.com,
kirill@...temov.name, linux-kernel@...r.kernel.org,
linux-mm@...ck.org, iamjoonsoo.kim@....com,
akpm@...ux-foundation.org, npiggin@...il.com
Subject: [PATCH v4 15/15] lockdep: Crossrelease feature documentation
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 <byungchul.park@....com>
---
Documentation/locking/crossrelease.txt | 1053 ++++++++++++++++++++++++++++++++
1 file changed, 1053 insertions(+)
create mode 100644 Documentation/locking/crossrelease.txt
diff --git a/Documentation/locking/crossrelease.txt b/Documentation/locking/crossrelease.txt
new file mode 100644
index 0000000..7170b2f
--- /dev/null
+++ b/Documentation/locking/crossrelease.txt
@@ -0,0 +1,1053 @@
+Crossrelease
+============
+
+Started by Byungchul Park <byungchul.park@....com>
+
+Contents:
+
+ (*) Background.
+
+ - What causes deadlock.
+ - What lockdep detects.
+ - How lockdep works.
+
+ (*) Limitation.
+
+ - Limit to typical locks.
+ - Pros from the limitation.
+ - Cons from the limitation.
+
+ (*) Generalization.
+
+ - Relax the limitation.
+
+ (*) Crossrelease.
+
+ - Introduce crossrelease.
+ - Pick true dependencies.
+ - Introduce commit.
+
+ (*) Implementation.
+
+ - Data structures.
+ - How crossrelease works.
+
+ (*) Optimizations.
+
+ - Avoid duplication.
+ - Lockless for hot paths.
+
+
+==========
+Background
+==========
+
+What causes deadlock
+--------------------
+
+A deadlock occurs when a context is waiting for an event to happen,
+which is impossible because another (or the) context who can trigger the
+event is also waiting for another (or the) event to happen, which is
+also impossible due to the same reason. Single or more contexts
+paricipate in such a deadlock.
+
+For example,
+
+ A context going to trigger event D is waiting for event A to happen.
+ A context going to trigger event A is waiting for event B to happen.
+ A context going to trigger event B is waiting for event C to happen.
+ A context going to trigger event C is waiting for event D to happen.
+
+A deadlock occurs when these four wait operations run at the same time,
+because event D cannot be triggered if event A does not happen, which in
+turn cannot be triggered if event B does not happen, which in turn
+cannot be triggered if event C does not happen, which in turn cannot be
+triggered if event D does not happen. After all, no event can be
+triggered since any of them never meets its precondition to wake up.
+
+In terms of dependency, a wait for an event creates a dependency if the
+context is going to wake up another waiter by triggering an proper event.
+In other words, a dependency exists if,
+
+ COND 1. There are two waiters waiting for each event at the same time.
+ COND 2. Only way to wake up each waiter is to trigger its events.
+ COND 3. Whether one can be woken up depends on whether the other can.
+
+Each wait in the example creates its dependency like,
+
+ Event D depends on event A.
+ Event A depends on event B.
+ Event B depends on event C.
+ Event C depends on event D.
+
+ NOTE: Precisely speaking, a dependency is one between whether a
+ waiter for an event can be woken up and whether another waiter for
+ another event can be woken up. However from now on, we will describe
+ a dependency as if it's one between an event and another event for
+ simplicity, so e.g. 'event D depends on event A'.
+
+And they form circular dependencies like,
+
+ -> D -> A -> B -> C -
+ / \
+ \ /
+ ---------------------
+
+ where A, B,..., D are different events, and '->' represents 'depends
+ on'.
+
+Such circular dependencies lead to a deadlock since no waiter can meet
+its precondition to wake up if they run simultaneously, as described.
+
+CONCLUSION
+
+Circular dependencies cause a deadlock.
+
+
+What lockdep detects
+--------------------
+
+Lockdep tries to detect a deadlock by checking dependencies created by
+lock operations e.i. acquire and release. Waiting for a lock to be
+released corresponds to waiting for an event to happen, and releasing a
+lock corresponds to triggering an event. See 'What causes deadlock'
+section.
+
+A deadlock actually occurs when all wait operations creating circular
+dependencies run at the same time. Even though they don't, a potential
+deadlock exists if the problematic dependencies exist. Thus it's
+meaningful to detect not only an actual deadlock but also its potential
+possibility. Lockdep does the both.
+
+Whether or not a deadlock actually occurs depends on several factors.
+For example, what order contexts are switched in is a factor. Assuming
+circular dependencies exist, a deadlock would occur when contexts are
+switched so that all wait operations creating the problematic
+dependencies run simultaneously.
+
+To detect a potential possibility which means a deadlock has not
+happened yet but might happen in future, lockdep considers all possible
+combinations of dependencies so that its potential possibility can be
+detected in advance. To do this, lockdep is trying to,
+
+1. Use a global dependency graph.
+
+ Lockdep combines all dependencies into one global graph and uses them,
+ regardless of which context generates them or what order contexts are
+ switched in. Aggregated dependencies are only considered so they are
+ prone to be circular if a problem exists.
+
+2. Check dependencies between classes instead of instances.
+
+ What actually causes a deadlock are instances of lock. However,
+ lockdep checks dependencies between classes instead of instances.
+ This way lockdep can detect a deadlock which has not happened but
+ might happen in future by others but the same classes.
+
+3. Assume all acquisitions lead to waiting.
+
+ Although locks might be acquired without waiting which is essential
+ to create dependencies, lockdep assumes all acquisitions lead to
+ waiting and generates dependencies, since it might be true some time
+ or another. Potential possibilities can be checked in this way.
+
+Lockdep detects both an actual deadlock and its possibility. But the
+latter is more valuable than the former. When a deadlock occurs actually,
+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 detects and reports,
+
+ 1. A deadlock possibility.
+ 2. A deadlock which actually occured.
+
+
+How lockdep works
+-----------------
+
+Lockdep does,
+
+ 1. Detect a new dependency created.
+ 2. Keep the dependency in a global data structure, graph.
+ 3. Check if circular dependencies exist.
+ 4. Report a deadlock or its possibility if so.
+
+A graph built by lockdep looks like, e.g.
+
+ A -> B - -> F -> G
+ \ /
+ -> E - -> L
+ / \ /
+ C -> D - -> H -
+ \
+ -> I -> K
+ /
+ J -
+
+ where A, B,..., L are different lock classes.
+
+Lockdep will add a dependency into graph when a new dependency is
+detected. For example, it will add a dependency 'K -> J' when a new
+dependency between lock K and lock J is detected. Then the graph will be,
+
+ A -> B - -> F -> G
+ \ /
+ -> E - -> L
+ / \ /
+ C -> D - -> H -
+ \
+ -> I -> K -
+ / \
+ -> J - \
+ / /
+ \ /
+ ------------------
+
+ where A, B,..., L are different lock classes.
+
+Now, circular dependencies are detected like,
+
+ -> I -> K -
+ / \
+ -> J - \
+ / /
+ \ /
+ ------------------
+
+ where J, I and K are different lock classes.
+
+As decribed in 'What causes deadlock', this is the condition under which
+a deadlock might occur. Lockdep detects a deadlock or its possibility by
+checking if circular dependencies were created after adding each new
+dependency into the global graph. This is the way how lockdep works.
+
+CONCLUSION
+
+Lockdep detects a deadlock or its possibility by checking if circular
+dependencies were created after adding each new dependency.
+
+
+==========
+Limitation
+==========
+
+Limit to typical locks
+----------------------
+
+Limiting lockdep to checking dependencies only on typical locks e.g.
+spin locks and mutexes, which should be released within the acquire
+context, the implementation of detecting and adding dependencies becomes
+simple but its capacity for detection becomes limited. Let's check what
+its pros and cons are, in next section.
+
+CONCLUSION
+
+Limiting lockdep to working on typical locks e.g. spin locks and mutexes,
+the implmentation becomes simple but limits its capacity.
+
+
+Pros from the limitation
+------------------------
+
+Given the limitation, when acquiring a lock, locks in the held_locks of
+the context cannot be released if the context fails to acquire it and
+has to wait for it. It also makes waiters for the locks in the
+held_locks stuck. It's the exact case to create a dependency 'A -> B',
+where lock A is each lock in held_locks and lock B is the lock to
+acquire. See 'What casues deadlock' section.
+
+For example,
+
+ CONTEXT 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, the held_locks of CONTEXT X is empty thus no
+dependency is added. When acquiring lock B, lockdep detects and adds
+a new dependency 'A -> B' between lock A in held_locks and lock B. When
+acquiring lock C, lockdep also adds another dependency 'B -> C' for the
+same reason. They can be simply added whenever acquiring each lock.
+
+And most data required by lockdep exists in a local structure e.i.
+'task_struct -> held_locks'. Forcing to access those data within the
+context, lockdep can avoid racy problems without explicit locks while
+handling the local data.
+
+Lastly, lockdep only needs to keep locks currently being held, to build
+the dependency graph. However relaxing the limitation, it might need to
+keep even locks already released, because the decision of whether they
+created dependencies might be long-deferred. See 'Crossrelease' section.
+
+To sum up, we can expect several advantages from the limitation.
+
+1. Lockdep can easily identify a dependency when acquiring a lock.
+2. Requiring only local locks makes many races avoidable.
+3. Lockdep only needs to keep locks currently being held.
+
+CONCLUSION
+
+Given the limitation, the implementation becomes simple and efficient.
+
+
+Cons from the limitation
+------------------------
+
+Given the limitation, lockdep is applicable only to typical locks. For
+example, page locks for page access or completions for synchronization
+cannot play with lockdep under the limitation.
+
+Can we detect deadlocks below, under the limitation?
+
+Example 1:
+
+ CONTEXT X CONTEXT 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 is a lock class and B is a page lock.
+
+No, we cannot.
+
+Example 2:
+
+ CONTEXT X CONTEXT Y CONTEXT 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 is a lock class and B is a page lock.
+
+No, we cannot.
+
+Example 3:
+
+ CONTEXT X CONTEXT 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 locks or completions.
+
+
+==============
+Generalization
+==============
+
+Relax the limitation
+--------------------
+
+Under the limitation, things to create dependencies are limited to
+typical locks. However, e.g. page locks and completions which are not
+typical locks also create dependencies and cause a deadlock. Therefore
+it would be better for lockdep to detect a deadlock or its possibility
+even for them.
+
+Detecting and adding 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. The more lockdep adds dependencies, the
+more it thoroughly works. Therefore Lockdep has to do its best to add as
+many true dependencies as possible into the graph.
+
+Relaxing the limitation, lockdep can add more dependencies since
+additional things e.g. page locks or completions create additional
+dependencies. However even so, it needs to be noted that the relaxation
+does not affect the behavior of adding dependencies for typical locks.
+
+For example, considering only typical locks, 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.
+
+On the other hand, under the relaxation, additional dependencies might
+be created and added. Assuming additional 'MX -> H', 'L -> NX' and
+'OX -> J' dependencies are added thanks to the relaxation, the graph
+will be, giving additional chances to check circular dependencies,
+
+ A -> B - -> F -> G
+ \ /
+ -> E - -> L -> NX
+ / \ /
+ C -> D - -> H -
+ / \
+ MX - -> I -> K
+ /
+ -> J -
+ /
+ OX -
+
+ where A, B,..., L, MX, NX and OX are different lock classes, and
+ a suffix 'X' is added on non-typical locks e.g. page locks and
+ completions.
+
+However, it might suffer performance degradation since relaxing the
+limitation with which design and implementation of lockdep could be
+efficient might introduce inefficiency inevitably. Each option, 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.
+
+The latter, of course, doesn't allow illegal contexts to release a lock.
+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
+circular dependencies, meaning a deadlock. Otherwise, any contexts are
+allowed to release it.
+
+CONCLUSION
+
+Relaxing the limitation, lockdep can add additional dependencies and
+get additional chances to check if they cause deadlocks.
+
+
+============
+Crossrelease
+============
+
+Introduce crossrelease
+----------------------
+
+To allow lockdep to handle additional dependencies by what might be
+released in any context, namely 'crosslock', a new feature 'crossrelease'
+is introduced. Thanks to the feature, now lockdep can identify such
+dependencies. Crossrelease feature has to do,
+
+ 1. Identify dependencies by crosslocks.
+ 2. Add the dependencies into graph.
+
+That's all. Once a meaningful dependency is added into graph, then
+lockdep would work with the graph as it did. So the most important thing
+crossrelease feature has to do is to correctly identify and add true
+dependencies into the global graph.
+
+A dependency e.g. 'A -> B' can be identified only in the A's release
+context because a decision required to identify the dependency can be
+made only in the release context. That is to decide whether A can be
+released so that a waiter for A can be woken up. It cannot be made in
+other contexts than the A's release context. See 'What causes deadlock'
+section to remind what a dependency is.
+
+It's no matter for typical locks because each acquire context is same as
+its release context, thus lockdep can decide whether a lock can be
+released, in the acquire context. However for crosslocks, lockdep cannot
+make the decision in the acquire context but has to wait until the
+release context is identified.
+
+Therefore lockdep has to queue all acquisitions which might create
+dependencies until the decision can be made, so that they can be used
+when it proves they are the right ones. We call the step 'commit'. See
+'Introduce commit' section.
+
+Of course, some actual deadlocks caused by crosslocks cannot be detected
+just when it happens, because the deadlocks cannot be identified until
+the crosslocks is actually released. However, deadlock possibilities can
+be detected in this way. It's worth possibility detection of deadlock.
+See 'What lockdep does' section.
+
+CONCLUSION
+
+With crossrelease feature, lockdep can work with what might be released
+in any context, namely crosslock.
+
+
+Pick true dependencies
+----------------------
+
+Remind what a dependency is. A dependency exists if,
+
+ COND 1. There are two waiters waiting for each event at the same time.
+ COND 2. Only way to wake up each waiter is to trigger its events.
+ COND 3. Whether one can be woken up depends on whether the other can.
+
+For example,
+
+ TASK X
+ ------
+ acquire A
+
+ acquire B /* A dependency 'A -> B' exists */
+
+ acquire C /* A dependency 'B -> C' exists */
+
+ release C
+
+ release B
+
+ release A
+
+ where A, B and C are different lock classes.
+
+A depedency 'A -> B' exists since,
+
+ 1. A waiter for A and a waiter for B might exist when acquiring B.
+ 2. Only way to wake up each of them is to release what it waits for.
+ 3. Whether the waiter for A can be woken up depends on whether the
+ other can. IOW, TASK X cannot release A if it cannot acquire B.
+
+Other dependencies 'B -> C' and 'A -> C' also exist for the same reason.
+But the second is ignored since it's covered by 'A -> B' and 'B -> C'.
+
+For another example,
+
+ TASK X TASK Y
+ ------ ------
+ acquire AX
+ acquire D
+ /* A dependency 'AX -> D' exists */
+ acquire B
+ release D
+ acquire C
+ /* A dependency 'B -> C' exists */
+ acquire E
+ /* A dependency 'AX -> E' exists */
+ acquire D
+ /* A dependency 'C -> D' exists */
+ release E
+ release D
+ release AX held by Y
+ release C
+
+ release B
+
+ where AX, B, C,..., E are different lock classes, and a suffix 'X' is
+ added on crosslocks.
+
+Even in this case involving crosslocks, the same rules can be applied. A
+depedency 'AX -> D' exists since,
+
+ 1. A waiter for AX and a waiter for D might exist when acquiring D.
+ 2. Only way to wake up each of them is to release what it waits for.
+ 3. Whether the waiter for AX can be woken up depends on whether the
+ other can. IOW, TASK X cannot release AX if it cannot acquire D.
+
+The same rules can be applied to other dependencies, too.
+
+Let's take a look at more complicated example.
+
+ TASK X TASK Y
+ ------ ------
+ acquire B
+
+ release B
+
+ acquire C
+
+ release C
+ (1)
+ fork Y
+ acquire AX
+ acquire D
+ /* A dependency 'AX -> D' exists */
+ acquire F
+ release D
+ acquire G
+ /* A dependency 'F -> G' exists */
+ acquire E
+ /* A dependency 'AX -> E' exists */
+ acquire H
+ /* A dependency 'G -> H' exists */
+ release E
+ release H
+ release AX held by Y
+ release G
+
+ release F
+
+ where AX, B, C,..., H are different lock classes, and a suffix 'X' is
+ added on crosslocks.
+
+Does a dependency 'AX -> B' exist? Nope.
+
+Two waiters, one is for AX and the other is for B, are essential
+elements to create the dependency 'AX -> B'. However in this example,
+these two waiters cannot exist at the same time. Thus the dependency
+'AX -> B' cannot be created.
+
+In fact, AX depends on all acquisitions after (1) in TASK X e.i. D and E,
+but excluding all acquisitions before (1) in the context e.i. A and C.
+Thus only 'AX -> D' and 'AX -> E' are true dependencies by AX.
+
+It would be ideal if the full set of true ones can be added. But parsing
+the whole code is necessary to do it, which is impossible. Relying on
+what actually happens at runtime, we can anyway add only true ones even
+though they might be a subset of the full set. This way we can avoid
+adding false ones.
+
+It's similar to how lockdep works for typical locks. Ideally there might
+be more true dependencies than ones being in the gloabl dependency graph,
+however, lockdep has no choice but to rely on what actually happens
+since otherwise it's almost impossible.
+
+CONCLUSION
+
+Relying on what actually happens, adding false dependencies can be
+avoided.
+
+
+Introduce commit
+----------------
+
+Crossrelease feature names it 'commit' to identify and add dependencies
+into graph in batches. Lockdep is already doing what commit is supposed
+to do, when acquiring a lock for typical locks. However, that way must
+be changed for crosslocks so that it identifies a crosslock's release
+context first, then does commit.
+
+There are four types of dependencies.
+
+1. TT type: 'Typical lock A -> Typical lock B' dependency
+
+ Just when acquiring B, lockdep can see it's in the A's release
+ context. So the dependency between A and B can be identified
+ immediately. Commit is unnecessary.
+
+2. TC type: 'Typical lock A -> Crosslock BX' dependency
+
+ Just when acquiring BX, lockdep can see it's in the A's release
+ context. So the dependency between A and BX can be identified
+ immediately. Commit is unnecessary, too.
+
+3. CT type: 'Crosslock AX -> Typical lock B' dependency
+
+ When acquiring B, lockdep cannot identify the dependency because
+ there's no way to know whether it's in the AX's release context. It
+ has to wait until the decision can be made. Commit is necessary.
+
+4. CC type: 'Crosslock AX -> Crosslock BX' dependency
+
+ If there is a typical lock acting as a bridge so that 'AX -> a lock'
+ and 'the lock -> BX' can be added, then this dependency can be
+ detected. But direct ways are not implemented yet. It's a future work.
+
+Lockdep works even without commit for typical locks. However, commit
+step is necessary once crosslocks are involved, until all crosslocks in
+progress are released. Introducing commit, lockdep performs three steps
+i.e. acquire, commit and release. What lockdep does in each step is,
+
+1. Acquire
+
+ 1) For typical lock
+
+ Lockdep does what it originally did and queues the lock so that
+ lockdep can check CT type dependencies using it at commit step.
+
+ 2) For crosslock
+
+ The crosslock is added to a global linked list so that lockdep can
+ check CT type dependencies using it at commit step.
+
+2. Commit
+
+ 1) For typical lock
+
+ N/A.
+
+ 2) For crosslock
+
+ Lockdep checks and adds CT Type dependencies using data saved at
+ acquire 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
+
+Crossrelease feature introduces commit step to handle dependencies by
+crosslocks in batches, which lockdep cannot handle in its original way.
+
+
+==============
+Implementation
+==============
+
+Data structures
+---------------
+
+Crossrelease feature introduces two main data structures.
+
+1. pend_lock
+
+ This is an array embedded in task_struct, for keeping locks queued so
+ that real dependencies can be added using them at commit step. Since
+ it's local data, it can be accessed locklessly in the owner context.
+ The array is filled at acquire step and consumed at commit step. And
+ it's managed in circular manner.
+
+2. cross_lock
+
+ This is a global linked list, for keeping all crosslocks in progress.
+ The list grows at acquire step and is shrunk at release step.
+
+CONCLUSION
+
+Crossrelease feature introduces 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 a 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 locks.
+
+ A's RELEASE CONTEXT (= A's ACQUIRE CONTEXT)
+ -------------------------------------------
+ acquire A
+
+ acquire B /* Add 'A -> B' */
+
+ acquire C /* Add 'B -> C' */
+
+ release C
+
+ release B
+
+ release A
+
+ where A, B and C are different lock classes.
+
+After adding 'A -> B', the dependency graph will be,
+
+ A -> B
+
+ where A and B are different lock classes.
+
+And after adding 'B -> C', the graph will be,
+
+ A -> B -> C
+
+ where A, B and C are different lock classes.
+
+What if we use commit step to add dependencies even for typical locks?
+Commit step is not necessary for them, however it anyway would work well,
+because this is a more general way.
+
+ A's RELEASE CONTEXT (= A's ACQUIRE CONTEXT)
+ -------------------------------------------
+ acquire A
+ /*
+ * 1. Mark A as started
+ * 2. Queue A
+ *
+ * In pend_lock: A
+ * In graph: Empty
+ */
+
+ acquire B
+ /*
+ * 1. Mark B as started
+ * 2. Queue B
+ *
+ * In pend_lock: A, B
+ * In graph: Empty
+ */
+
+ acquire C
+ /*
+ * 1. Mark C as started
+ * 2. Queue C
+ *
+ * In pend_lock: A, B, C
+ * In graph: Empty
+ */
+
+ release C
+ /*
+ * 1. Commit C (= Add 'C -> ?')
+ * a. What queued since C was marked: Nothing
+ * b. Add nothing
+ *
+ * In pend_lock: A, B, C
+ * In graph: Empty
+ */
+
+ release B
+ /*
+ * 1. Commit B (= Add 'B -> ?')
+ * a. What queued since B was marked: C
+ * b. Add 'B -> C'
+ *
+ * In pend_lock: A, B, C
+ * In graph: 'B -> C'
+ */
+
+ release A
+ /*
+ * 1. Commit A (= Add 'A -> ?')
+ * a. What queued since A was marked: B, C
+ * b. Add 'A -> B'
+ * c. Add 'A -> C'
+ *
+ * In pend_lock: A, B, C
+ * In graph: 'B -> C', 'A -> B', 'A -> C'
+ */
+
+ where A, B and C are different lock classes.
+
+After doing commit A, B and C, the dependency graph becomes like,
+
+ A -> B -> C
+
+ where A, B and C are different lock classes.
+
+ NOTE: A dependency 'A -> C' is optimized out.
+
+We can see the former graph built without commit step is same as the
+latter graph built using commit steps. Of course the former way leads to
+earlier finish for building the graph, 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 for crosslocks.
+
+Let's look at how commit works for crosslocks.
+
+ AX's RELEASE CONTEXT AX's ACQUIRE CONTEXT
+ -------------------- --------------------
+ acquire AX
+ /*
+ * 1. Mark AX as started
+ *
+ * (No queuing for crosslocks)
+ *
+ * In pend_lock: Empty
+ * In graph: Empty
+ */
+
+ (serialized by some means e.g. barrier)
+
+ acquire D
+ /*
+ * (No marking for typical locks)
+ *
+ * 1. Queue D
+ *
+ * In pend_lock: D
+ * In graph: Empty
+ */
+ acquire B
+ /*
+ * (No marking for typical locks)
+ *
+ * 1. Queue B
+ *
+ * In pend_lock: B
+ * In graph: Empty
+ */
+ release D
+ /*
+ * (No commit for typical locks)
+ *
+ * In pend_lock: D
+ * In graph: Empty
+ */
+ acquire C
+ /*
+ * (No marking for typical locks)
+ *
+ * 1. Add 'B -> C' of TT type
+ * 2. Queue C
+ *
+ * In pend_lock: B, C
+ * In graph: 'B -> C'
+ */
+ acquire E
+ /*
+ * (No marking for typical locks)
+ *
+ * 1. Queue E
+ *
+ * In pend_lock: D, E
+ * In graph: 'B -> C'
+ */
+ acquire D
+ /*
+ * (No marking for typical locks)
+ *
+ * 1. Add 'C -> D' of TT type
+ * 2. Queue D
+ *
+ * In pend_lock: B, C, D
+ * In graph: 'B -> C', 'C -> D'
+ */
+ release E
+ /*
+ * (No commit for typical locks)
+ *
+ * In pend_lock: D, E
+ * In graph: 'B -> C', 'C -> D'
+ */
+ release D
+ /*
+ * (No commit for typical locks)
+ *
+ * In pend_lock: B, C, D
+ * In graph: 'B -> C', 'C -> D'
+ */
+ release AX
+ /*
+ * 1. Commit AX (= Add 'AX -> ?')
+ * a. What queued since AX was marked: D, E
+ * b. Add 'AX -> D' of CT type
+ * c. Add 'AX -> E' of CT type
+ *
+ * In pend_lock: D, E
+ * In graph: 'B -> C', 'C -> D',
+ * 'AX -> D', 'AX -> E'
+ */
+ release C
+ /*
+ * (No commit for typical locks)
+ *
+ * In pend_lock: B, C, D
+ * In graph: 'B -> C', 'C -> D',
+ * 'AX -> D', 'AX -> E'
+ */
+
+ release B
+ /*
+ * (No commit for typical locks)
+ *
+ * In pend_lock: B, C, D
+ * In graph: 'B -> C', 'C -> D',
+ * 'AX -> D', 'AX -> E'
+ */
+
+ where AX, B, C,..., E are different lock classes, and a suffix 'X' is
+ added on crosslocks.
+
+When acquiring crosslock AX, crossrelease feature marks AX as started,
+which means all acquisitions from now are candidates which might create
+dependencies with AX. True dependencies will be determined when
+identifying the AX's release context.
+
+When acquiring typical lock B, lockdep queues B so that it can be used
+at commit step later since any crosslocks in progress might depends on B.
+The same thing is done on lock C, D and E. And then two dependencies
+'AX -> D' and 'AX -> E' are added at commit step, when identifying the
+AX's release context.
+
+The final graph is, with crossrelease feature using commit,
+
+ B -> C -
+ \
+ -> D
+ /
+ AX -
+ \
+ -> E
+
+ where AX, B, C,..., E are different lock classes, and a suffix 'X' is
+ added on crosslocks.
+
+However, without crossrelease feature, the final graph would be,
+
+ B -> C -> D
+
+ where B and C are different lock classes.
+
+The former graph has two more dependencies 'AX -> D' and 'AX -> E'
+giving additional chances to check if they cause deadlocks. This way
+lockdep can detect a deadlock or its possibility caused by crosslocks.
+Again, crossrelease feature does not affect the behavior of adding
+dependencies for typical locks.
+
+CONCLUSION
+
+Crossrelease works well for crosslock, thanks to commit step.
+
+
+=============
+Optimizations
+=============
+
+Avoid duplication
+-----------------
+
+Crossrelease feature uses a cache like what lockdep is already using for
+dependency chains, but this time it's for caching a dependency of CT
+type, crossing between two different context. Once that dependency is
+cached, same dependencies will never be added again. Queueing
+unnecessary locks is also prevented based on the cache.
+
+CONCLUSION
+
+Crossrelease does not add any duplicate dependencies.
+
+
+Lockless for hot paths
+----------------------
+
+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 the accesses to happen only within the owner context.
+It's like how lockdep accesses held_locks. Lockless implmentation is
+important since typical locks are very frequently acquired and released.
+
+CONCLUSION
+
+Crossrelease is designed to use no lock for hot paths.
+
--
1.9.1
Powered by blists - more mailing lists