lkml.org 
[lkml]   [2020]   [Aug]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    Subject[RFC v7 00/19] lockdep: Support deadlock detection for recursive read locks
    Date
    Hi Peter and Waiman,

    As promised, this is the updated version of my previous lockdep patchset
    for recursive read lock support. It's based on v5.8. Previous versions
    can be found at:

    V1: https://marc.info/?l=linux-kernel&m=150393341825453
    V2: https://marc.info/?l=linux-kernel&m=150468649417950
    V3: https://marc.info/?l=linux-kernel&m=150637795424969
    V4: https://marc.info/?l=linux-kernel&m=151550860121565
    V5: https://marc.info/?l=linux-kernel&m=151928315529363
    V6: https://lore.kernel.org/lkml/20180411135110.9217-1-boqun.feng@gmail.com/

    Changes since last version:

    * I change the detection algorithm which I present in 2018
    plumbers [1], you can find the explanation of the detection
    method in patch #2.

    * Adjust the irq safe->unsafe changes from Frederic Weisbecker

    * Add more tests.


    As Peter pointed out:

    https://marc.info/?l=linux-kernel&m=150349072023540

    The lockdep current has a limit support for recursive read locks, the
    deadlock case as follow could not be detected:

    read_lock(A);
    lock(B);
    lock(B);
    write_lock(A);

    I got some inspiration from Gautham R Shenoy:

    https://lwn.net/Articles/332801/

    , and came up with this series.

    The basic idea is:

    * Add recursive read locks into the graph

    * Classify dependencies into -(SR)->, -(ER)->, -(SN)->,
    -(EN)->, where R stands for recursive read lock, N stands for
    other locks(i.e. non-recursive read locks and write locks), S
    stands for shared locks (read locks, no matter recursive or
    not), and E stands for exclusive locks (i.e. write locks)

    * Define strong dependency paths as the paths of dependencies
    don't have two adjacent dependencies as -(*R)-> and -(S*)->.

    * Extend __bfs() to only traverse on strong dependency paths.

    * If __bfs() finds a strong dependency circle, then a deadlock is
    reported.

    The whole series consists of 19 patches:

    1. Add documentation for recursive read lock deadlock detection
    reasoning

    2. Annotate read_lock() correctly (with queued_read_lock()
    semantics into consideration)

    3. Do a clean up on the return value of __bfs() and its friends.

    4. Make __bfs() able to visit every dependency until a match is
    found. The old version of __bfs() could only visit each lock
    class once, and this is insufficient if we are going to add
    recursive read locks into the dependency graph.

    5. Reduce the size of lock_list::distance.

    6-7 Extend __bfs() to be able to traverse the stong dependency
    patchs after recursive read locks added into the graph.

    8. Make __bfs(.math) return bool.

    9-11 Adjust check_redundant(), check_noncircular() and
    check_irq_usage() with recursive read locks into consideration.

    12. Finally add recursive read locks into the dependency graph.

    13-14 Adjust lock cache chain key generation with recursive read locks
    into consideration, and provide a test case.

    15-16 Add more test cases.

    17. Revert commit d82fed752942 ("locking/lockdep/selftests: Fix
    mixed read-write ABBA tests"),

    18-19 Add more test cases (including tests that are specific for
    queued_read_lock())

    This series passed all the lockdep selftest cases (including those I
    introduce).

    Test and comments are welcome!

    Regards,
    Boqun

    \
     
     \ /
      Last update: 2020-08-07 09:43    [W:3.394 / U:0.668 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site