lkml.org 
[lkml]   [2019]   [Aug]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH v4 24/30] locking/lockdep: Define the two task model for lockdep checks formally
    Date
    Lockdep effectively uses a two-task model to track workload's locking
    behavior and then do the checking to find inversion deadlock scenarios
    based on such model. Lets explain it in detail.

    When there is a new lock dependency L1 -> L2 (i.e., the current task
    attempts to acquire L2 while holding L1), which is from a new lock
    chain's latest two locks, lockdep's view of the world is composed of two
    virtual tasks:

    - Task1: the entire previous locking behavior depicted by the forward
    lock dependency graph.

    - Task2: the current task's new locking behavior, i.e., the L1 -> L2 dependency.

    Whenever a Task2 comes, lockdep tries to find in Task1 whether there exists
    the inverse locking order of L1 -> L2, namely L2 -> L1. If this inverse
    locking order exists, then lockdep has found the typical inversion deadlock
    scenario, a.k.a, ABBA deadlock. And if not, Task2 will be merged into Task1
    to become a new bigger Task1 with a bigger graph. Then this track and check
    cycle goes on and on.

    There is some nuances between this two-task model and the real workload
    locking behavior. Some examples:

    (The following Tx denotes concrete tasks)

    T1
    --

    L1
    L2

    (L1 and L2 released)

    L2
    L3

    T2
    --

    L1
    L2
    L3

    T1 and T2 will produce the same Task1 from the perspective of lockdep's
    two-task model. However, this model does not actually reflect the reality in
    full length. In T1, L1 -> L3 actually has no "real" dependency while in T2
    it is "real" (a real X -> Y lock dependency is defined as a task is
    attempting to acquire Y while holding X). This may result in false positive
    deadlock scenarios. For example:

    Case #1.1:

    T1 T2
    -- --

    L1
    L2 L3
    L3 L1 [Deadlock]

    Case #1.2 (T1 is a singular task):

    T1 T2
    -- --

    L1
    L2

    (L1 L2 released)

    L2 L3
    L3 L1 [No deadlock]

    Case #1.3:

    T1a T1b T2
    --- --- --

    L1 L1
    L2 L2

    (L1 L2 released
    in T1a and T1b)

    L2 L2 L3
    L3 L3 L1 [Deadlock]

    From Case #1.2 (no deadlock) to Case #1.3 (deadlock), we can see that
    lockdep is also assuming there can be multiple Task1's on top of the
    two-task model, and from pragmatic point of view, this assumption is not
    unrealistic to make.

    However, with read locks that can be fully concurrent with read locks
    and not be blocked by write locks (such as the rwlock). Lockdep's such
    model is flawed. For example (the following read locks, denoted as RR,
    and write locks are of type rwlock):

    Case #2.1:

    T1 T2
    -- --

    W1
    RR2 W3
    W3 W1 [Deadlock]

    Case #2.2:

    T1a T1b T2
    --- --- --

    W1 RR2 W3
    RR2 W3 W1 [No deadlock]

    Case #2.3:

    T1a T1b T2
    --- --- --

    W1 W1
    RR2 RR2

    (W1 RR2 released
    in T1a and T1b)

    RR2 RR2 W3
    W3 W3 W1 [No deadlock]

    Lockdep cannot differentiate Case #2.1 from Case #2.2 and Case #2.3 or
    vice versa. This is because when modeling Task1, it cannot tell whether
    two neighboring direct dependencies in the graph are in the same real
    task and hence create a "real" dependency.

    To make up for this, the two-task model needs to be strengthened. We
    previously mapped lock chains to lock dependency graph and added
    read-write lock types into dependencies. This patch finally modifies the
    graph traversing algorithm (__bfs()) to stop when two neighboring direct
    dependencies are not in the same lock chain and the middle lock is a
    recursive-read lock (rwlock).

    Signed-off-by: Yuyang Du <duyuyang@gmail.com>
    ---
    kernel/locking/lockdep.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++
    1 file changed, 68 insertions(+)

    diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
    index 3ad97bc..05c70be 100644
    --- a/kernel/locking/lockdep.c
    +++ b/kernel/locking/lockdep.c
    @@ -1617,6 +1617,71 @@ static inline void set_lock_type2(struct lock_list *lock, int read)
    }

    /*
    + * A lock stopper in the dependency graph is a read lock that stops the
    + * graph traversal passing through it even if the two dependencies are
    + * linked in a path. A stopper sits in such two lock dependencies:
    + *
    + * X -> RR (stopper) -> X (where RR is recursive-read lock)
    + *
    + * and these two dependencies are NOT from one lock chain.
    + */
    +static inline bool
    +read_lock_stopper(struct lock_list *parent, struct lock_list *child, int forward)
    +{
    + struct lock_chain *chain1, *chain2;
    + struct lock_list *list[2] = { child, parent };
    + u64 key1, key2;
    + int distance, other = 1 - forward;
    +
    + /* This is the source entry */
    + if (!get_lock_parent(parent))
    + return false;
    +
    + if (!(get_lock_type1(list[other]) == LOCK_TYPE_RECURSIVE &&
    + get_lock_type2(list[forward]) == LOCK_TYPE_RECURSIVE))
    + return false;
    +
    + distance = list[forward]->distance;
    +
    + list_for_each_entry_rcu(chain1, &list[forward]->chains, chain_entry) {
    + key1 = chain1->chain_key;
    +
    + list_for_each_entry_rcu(chain2, &list[other]->chains, chain_entry) {
    + /*
    + * If the two chains are in the same task lock stack,
    + * we should be able to calculate key2 from key1 if
    + * distance is 1, or calculate key1 from key2 if
    + * distance is larger than 1.
    + */
    + if (distance == 1) {
    + int class_idx = fw_dep_class(list[other]) - lock_classes;
    + key1 = iterate_chain_key(key1, class_idx,
    + get_lock_type2(list[other]));
    + key2 = chain2->chain_key;
    +
    + if (key1 == key2)
    + return false;
    + }
    + else {
    + int i = chain1->base, j = chain2->base;
    +
    + if (chain1->depth != chain2->depth - distance)
    + continue;
    +
    + for (; i < chain1->depth - 1; i++, j++)
    + if (chain_hlocks[i] != chain_hlocks[j] ||
    + chain_hlocks_type[i] != chain_hlocks_type[i])
    + continue;
    +
    + return false;
    + }
    + }
    + }
    +
    + return true;
    +}
    +
    +/*
    * Forward- or backward-dependency search, used for both circular dependency
    * checking and hardirq-unsafe/softirq-unsafe checking.
    */
    @@ -1656,6 +1721,9 @@ static int __bfs(struct lock_list *source_entry,
    if (!lock_accessed(entry, forward)) {
    unsigned int cq_depth;

    + if (read_lock_stopper(lock, entry, forward))
    + continue;
    +
    mark_lock_accessed(entry, lock, forward);

    if (__cq_enqueue(cq, entry)) {
    --
    1.8.3.1
    \
     
     \ /
      Last update: 2019-08-29 10:34    [W:7.982 / U:0.048 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site