lkml.org 
[lkml]   [2021]   [Aug]   [2]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    Subject[RFC] Cross-release versus a new tool
    Hi folks,

    Lockdep is a great tool for detecting deadlock possibility, which was
    designed for detecting wrong usage of locking API esp. typical lock e.g.
    spinlock and mutex. However, when it comes to read lock or any other
    mechanisms than typical lock, Lockdep code has been getting tweaked and
    complicated to cover all of them. It'd be getting worse over time.

    First of all, we should understand what a deadlock detection tool should
    do. Fundamentally, a deadlock is caused by "WAITER(S) ON ITS EVENT(S)
    THAT WILL NEVER HAPPEN" so the tool should focus on waiters and events.
    Otherwise, complexifying it just makes things worse.

    (NOTE: I hope you guys distinguish between dependency checking feature
    and any other supports for lock usage. I'm gonna talk about the aspect
    of dependency checking feature only in this posting. The support for
    correctness check of lock usage should still be there as is.)

    We can detect a deadlock by tracking waiters and its events. A deadlock
    detection tool should focus on waiters and events and its contexts, not
    specific cases like the order of acquisitions that Lockdep does, where
    waiters and its events *implicitly* exist there anyway. This way, the
    tool can be simple and straightforward, and able to cover all cases.

    I understand all Linux kernel features should be mature enough. I think
    Lockdep is fairly so, thanks to the folks for many years. I partially
    agree with the opinion that Lockdep should be kept and new feautures for
    a better work should be stacked onto Lockdep if needed. However, it's
    a shame that the base that Lockdep was built on is not that nice.

    The requirement we expect the tool should meet is, I think:

    R1. It should detect a deadlock caused by typical type of lock e.g.
    spin lock and mutex lock.

    We acquire a lock before accessing a shared resource and release
    the lock after using it, say, both the acquisition and release
    happen at the *same context*. Using the fact so just tracking the
    order of lock acquisitions, we can detect a deadlock.

    R2. It should detect a deadlock caused by other than typical type of
    lock e.g. read lock.

    Read lock works in a different way from typical one because it
    was introduced to avoid *wait* on contention between read locks.
    Furthermore, they behave differently depending on if it's
    recursive one or not. It's not easy to detect a deadlock with
    focusing on the order unless focusing on the interesting waiters
    and its events. Otherwise, the tool should be tweaked and getting
    complicated to cover them, which is how Lockdep does :(

    R3. It should detect a deadlock caused by any waiter e.g. page lock
    and wait_for_completion.

    Not only locks but also any waits can cause a deadlock. However,
    Lockdep doesn't work for the cases because it wasn't designed
    fot that. Instead, these cases have been covered by manually
    adding Lockdep annotations like acquire/release, in case by case
    manner when found the needs. It'd better be done automatically or
    with simpler annotations, for example, wait/event annotation
    instead of acquire/release.

    R4. Sychronization objects e.g. lock and wait_for_completion need to
    be classified correctly as a prerequisite, minimizing the number
    of false positives.

    A deadlock detection tool does not track all individual objects.
    Instead, it works with *class* classified based on its code path
    basically. Unfortunately, because not all the classification is
    perfect, false alarms may raise. To avoid it, some classes that
    were assigned automatically but incorrectly, have been reset by
    the developers manually for many years.

    R5. It should not overwhelm the kernel message with meaningless
    reports. But it should still report meaningful ones.

    Even though one problematic usage in terms of dependency can
    cause more than one scenario leading deadlock, it would be
    meaningless to report all of them because some may rather get in
    the way when picking meaningful ones for analysis. However,
    meaningful ones are still worth being reported.

    R6. It should be mature and stable enough to handle subtle issues
    properly.

    There are a lot of subtle issues in Linux kernel. The more
    primitives they are, the more subtle issues there might be. A
    dependency checking tool is one of very primitives feature so
    needs to be mature and stable enough.

    Lockdep has been developed fairly great for many years - by intoducing
    dynamic class assignment feature, recursive read lock support lately and
    so on - so as to cover R1, R2, R4, partially R5 and R6 for now, but,
    with the code complicated and enlarged inevitably.

    However, there is still a lack of R3 in the tool. I'm thinking we can
    choose one of two options to cover R3:

    1. Cross-release

    This feature was reverted due to a few false positive alarms in a
    specific environment where more than one file system were stacked on
    one another through loopback. At that time, it looked not easy to
    assign proper classes to locks in each layer with a lack of dynamic
    class assignment feature. Now it's been ready, I think it's worth
    retrying to introduce Cross-release.

    We can keep the all advantages Lockdep already has, esp. R6 with this
    option. At the same time, we would keep the problems too, Lockdep has
    e.i. the code is going more complicated and getting bigger than what
    it actually needs.

    2. A new tool

    I implemented a deadlock detection tool from the scratch by tracking
    waits and event, not acquisition or release - it was inevitable to
    rely on BFS as Lockdep does tho. I should admit this is not as mature
    as Lockdep so needs to be improved more esp. stability. However, I'm
    strongly convinced that it's the right way to go with and it does
    exactly what a deadlock detection tool should do.

    However, again, the new tool has just been implemented so may not
    cover R6 enough. So I need you guys to work together... FYI, see the
    link, https://lkml.org/lkml/2020/11/23/236 for the patches. The work
    is based on the mainline v5.9.

    NOTE: It's worth noting that the new tool is not perfect for now. For
    example, it has yet to support non-recursive read lock depenency. It
    would not be that hard work tho.

    I've asked you for your opinion in https://lkml.org/lkml/2020/11/11/19
    one day, and someone answered like re-introducing Cross-release looks
    better. However, I decided to write this posting again and lastly
    because I thought I didn't explain the rationale, each pros and cons
    enough. Just this last time and then I'll stop asking any more.

    It would not be that important to doing something onto the kernel code
    but the right direction definitely should be more important. I want to
    discuss the direction and decision wrt the tool based on the facts, good
    things, and bad things without bias. Whatever decision will be made, I'd
    like to go work with it and ask you for working together once it's made.

    Either Cross-release or the new tool, let me go with any. Could you give
    your opinions? It would be appreciated.

    Thank you!
    Byungchul

    ---

    P.S. Trivial thing... but I'd like to mention one thing. From what I
    heard, you got overwhelmed by a ton of reports when you allowed Lockdep
    to multi-report. It's because Lockdep is not designed to work nicely
    with irq related deadlock like "irq enable -> acqusition within the irq"
    cases. It's gonna certainly overwhelm kmsg with the current design.

    When it comes to irq related deadlock, it would be a better decision to
    report only the shortest path in the dependency tree - assuming the tree
    reflects irq related dependencies as well - which means the most likely
    case. I tested the test case and found it didn't overwhelm even with
    multiple reporting on.

    Multiple reporting with Dept looks quite helpful from my experience. If
    you doubt, I'd recommend to try to see what's gonna happen with Dept on
    v5.9 with your system. Refer to the link above for the patches.

    \
     
     \ /
      Last update: 2021-08-03 04:47    [W:3.464 / U:1.284 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site