[RFC] Cross-release versus a new tool

[Byungchul Park]

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.