Messages in this thread | | | Date | Tue, 3 Aug 2021 11:16:12 +0900 | From | Byungchul Park <> | 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.
| |