Re: [RFC] Are you good with Lockdep?
On Mon, Nov 16, 2020 at 03:37:29PM +, Matthew Wilcox wrote: > > > Something I believe lockdep is missing is a way to annotate "This lock > > > will be released by a softirq". If we had lockdep for lock_page(), this > > > would be a great case to show off. The filesystem locks the page, then > > > submits it to a device driver. On completion, the filesystem's bio > > > completion handler will be called in softirq context and unlock the page. > > > > > > So if the filesystem has another lock which is acquired by the completion > > > handler. we could get an ABBA deadlock that lockdep would be unable to > > > see. > > > > > > There are other similar things; if you look at the remaining semaphore > > > users in the kernel, you'll see the general pattern is that they're > > > acquired in process context and then released in interrupt context. > > > If we had a way to transfer ownership of the semaphore to a generic > > > "interrupt context", they could become mutexes and lockdep could check > > > that nothing else will cause a deadlock. > > > > Yes. Those are exactly what Cross-release feature solves. Those problems > > can be achieved with Cross-release. But even with Cross-release, we > > still cannot solve the problem of (1) readlock handling (2) and false > > positives preventing further reporting. > > It's not just about lockdep for semaphores. Mutexes will spin if the > current owner is still running, so to convert an interrupt-released > semaphore to a mutex, we need a way to mark the mutex as being released > by the new owner. > > I really don't think you want to report subsequent lockdep splats. Don't you think it would be ok if the # of splats is not too many? Or is it still a problem even if not? We shouldn't do that if it clearly makes a big problem. Otherwise, it should be because any deadlock detection tool cannot be enhanced to be stonger which inevitably produces false positives until proper keys are assigned to all classes in the kernel, unless multiple reports are allowed. Could you explain why? It would be appreciated. Thanks, Byungchul
Re: [RFC] Are you good with Lockdep?
On Mon, Nov 16, 2020 at 06:05:47PM +0900, Byungchul Park wrote: > On Thu, Nov 12, 2020 at 11:58:44PM +0900, Byungchul Park wrote: > > > > FYI, roughly Lockdep is doing: > > > > > > > >1. Dependency check > > > >2. Lock usage correctness check (including RCU) > > > >3. IRQ related usage correctness check with IRQFLAGS > > > > > > > > 2 and 3 should be there forever which is subtle and have gotten matured. > > > > But 1 is not. I've been talking about 1. But again, it's not about > > > > replacing it right away but having both for a while. I'm gonna try my > > > > best to make it better. > > > > > > And I believe lockdep does handle 1. Perhaps show some tangible use case > > > that you want to cover that you do not believe that lockdep can handle. If > > > lockdep cannot handle it, it will show us where lockdep is lacking. If it > > > can handle it, it will educate you on other ways that lockdep can be > > > helpful in your development ;-) > > 1) OK. Lockdep might work with trylock well. > 2) Definitely Lockdep cannot do what Cross-release was doing. > 3) For readlock handling, let me be back later and give you examples. I >need check current Lockdep code first. But I have to all-stop what >I'm doing at the moment because of a very big personal issue, which >is a sad thing. I just found that Boqun Feng has made a lot of changes into Lockdep recently to support tracking recursive read locks, while I was checking how the current Lockdep deals with read locks. I need to read the code more.. I'll add my opinion on it once I see how it works. Before that, I'd like to share my approach so that you guys can see what means to track *wait* and *event*, how simply the tool can work and what exactly a deadlock detection tool should do. Let me add my patches onto this thread right away. I understand you all don't want to replace such a stable tool but I hope you to see *the* right way to track things for that purpose. Again, I do never touch any other functions of Lockdep including all great efforts that have been made but dependency tracking. Thanks, Byungchul
Re: [RFC] Are you good with Lockdep?
On Wed, Nov 18, 2020 at 09:45:40AM +0800, Boqun Feng wrote: > Hi Matthew, > > On Mon, Nov 16, 2020 at 03:37:29PM +, Matthew Wilcox wrote: > [...] > > > > It's not just about lockdep for semaphores. Mutexes will spin if the > > current owner is still running, so to convert an interrupt-released > > semaphore to a mutex, we need a way to mark the mutex as being released > > Could you provide an example for the conversion from interrupt-released > semaphore to a mutex? I'd like to see if we can improve lockdep to help > on that case. How about adb_probe_mutex in drivers/macintosh/adb.c. Most of the acquires/releases are within the same task. But adb_reset_bus() calls down(_probe_mutex), then schedules adb_reset_work() which runs adb_probe_task() which calls up(_probe_mutex). Ideally adb_probe_mutex would become a mutex instead of the semaphore it currently is. adb_reset_bus() would pass ownership of the mutex to kadbprobe since it's the one which must run in order to release the mutex.
Re: [RFC] Are you good with Lockdep?
Hi Matthew, On Mon, Nov 16, 2020 at 03:37:29PM +, Matthew Wilcox wrote: [...] > > It's not just about lockdep for semaphores. Mutexes will spin if the > current owner is still running, so to convert an interrupt-released > semaphore to a mutex, we need a way to mark the mutex as being released Could you provide an example for the conversion from interrupt-released semaphore to a mutex? I'd like to see if we can improve lockdep to help on that case. Regards, Boqun > by the new owner. > > I really don't think you want to report subsequent lockdep splats.
Re: [RFC] Are you good with Lockdep?
On Mon, Nov 16, 2020 at 05:57:57PM +0900, Byungchul Park wrote: > On Thu, Nov 12, 2020 at 02:52:51PM +, Matthew Wilcox wrote: > > On Thu, Nov 12, 2020 at 09:26:12AM -0500, Steven Rostedt wrote: > > > > FYI, roughly Lockdep is doing: > > > > > > > >1. Dependency check > > > >2. Lock usage correctness check (including RCU) > > > >3. IRQ related usage correctness check with IRQFLAGS > > > > > > > > 2 and 3 should be there forever which is subtle and have gotten matured. > > > > But 1 is not. I've been talking about 1. But again, it's not about > > > > replacing it right away but having both for a while. I'm gonna try my > > > > best to make it better. > > > > > > And I believe lockdep does handle 1. Perhaps show some tangible use case > > > that you want to cover that you do not believe that lockdep can handle. If > > > lockdep cannot handle it, it will show us where lockdep is lacking. If it > > > can handle it, it will educate you on other ways that lockdep can be > > > helpful in your development ;-) > > > > Something I believe lockdep is missing is a way to annotate "This lock > > will be released by a softirq". If we had lockdep for lock_page(), this > > would be a great case to show off. The filesystem locks the page, then > > submits it to a device driver. On completion, the filesystem's bio > > completion handler will be called in softirq context and unlock the page. > > > > So if the filesystem has another lock which is acquired by the completion > > handler. we could get an ABBA deadlock that lockdep would be unable to see. > > > > There are other similar things; if you look at the remaining semaphore > > users in the kernel, you'll see the general pattern is that they're > > acquired in process context and then released in interrupt context. > > If we had a way to transfer ownership of the semaphore to a generic > > "interrupt context", they could become mutexes and lockdep could check > > that nothing else will cause a deadlock. > > Yes. Those are exactly what Cross-release feature solves. Those problems > can be achieved with Cross-release. But even with Cross-release, we > still cannot solve the problem of (1) readlock handling (2) and false > positives preventing further reporting. It's not just about lockdep for semaphores. Mutexes will spin if the current owner is still running, so to convert an interrupt-released semaphore to a mutex, we need a way to mark the mutex as being released by the new owner. I really don't think you want to report subsequent lockdep splats.
Re: [RFC] Are you good with Lockdep?
On Thu, Nov 12, 2020 at 11:58:44PM +0900, Byungchul Park wrote: > > > FYI, roughly Lockdep is doing: > > > > > >1. Dependency check > > >2. Lock usage correctness check (including RCU) > > >3. IRQ related usage correctness check with IRQFLAGS > > > > > > 2 and 3 should be there forever which is subtle and have gotten matured. > > > But 1 is not. I've been talking about 1. But again, it's not about > > > replacing it right away but having both for a while. I'm gonna try my > > > best to make it better. > > > > And I believe lockdep does handle 1. Perhaps show some tangible use case > > that you want to cover that you do not believe that lockdep can handle. If > > lockdep cannot handle it, it will show us where lockdep is lacking. If it > > can handle it, it will educate you on other ways that lockdep can be > > helpful in your development ;-) 1) OK. Lockdep might work with trylock well. 2) Definitely Lockdep cannot do what Cross-release was doing. 3) For readlock handling, let me be back later and give you examples. I need check current Lockdep code first. But I have to all-stop what I'm doing at the moment because of a very big personal issue, which is a sad thing. Sorry for the late response. Thank you, Byungchul > > Yes. That's the best thing I can do for all of us. I will. > > I already did exactly the same thing while I was developing cross-release. > But I'm willing to do it again with the current Lockdep code. > > But not today. It's over mid-night. Good night~ > > -- > Thanks, > Byungchul
Re: [RFC] Are you good with Lockdep?
On Thu, Nov 12, 2020 at 02:52:51PM +, Matthew Wilcox wrote: > On Thu, Nov 12, 2020 at 09:26:12AM -0500, Steven Rostedt wrote: > > > FYI, roughly Lockdep is doing: > > > > > >1. Dependency check > > >2. Lock usage correctness check (including RCU) > > >3. IRQ related usage correctness check with IRQFLAGS > > > > > > 2 and 3 should be there forever which is subtle and have gotten matured. > > > But 1 is not. I've been talking about 1. But again, it's not about > > > replacing it right away but having both for a while. I'm gonna try my > > > best to make it better. > > > > And I believe lockdep does handle 1. Perhaps show some tangible use case > > that you want to cover that you do not believe that lockdep can handle. If > > lockdep cannot handle it, it will show us where lockdep is lacking. If it > > can handle it, it will educate you on other ways that lockdep can be > > helpful in your development ;-) > > Something I believe lockdep is missing is a way to annotate "This lock > will be released by a softirq". If we had lockdep for lock_page(), this > would be a great case to show off. The filesystem locks the page, then > submits it to a device driver. On completion, the filesystem's bio > completion handler will be called in softirq context and unlock the page. > > So if the filesystem has another lock which is acquired by the completion > handler. we could get an ABBA deadlock that lockdep would be unable to see. > > There are other similar things; if you look at the remaining semaphore > users in the kernel, you'll see the general pattern is that they're > acquired in process context and then released in interrupt context. > If we had a way to transfer ownership of the semaphore to a generic > "interrupt context", they could become mutexes and lockdep could check > that nothing else will cause a deadlock. Yes. Those are exactly what Cross-release feature solves. Those problems can be achieved with Cross-release. But even with Cross-release, we still cannot solve the problem of (1) readlock handling (2) and false positives preventing further reporting. Thanks, Byungchul
Re: [RFC] Are you good with Lockdep?
On Thu, Nov 12, 2020 at 02:56:49PM +0100, Daniel Vetter wrote: > > > I think I understand it. For things like completions and other "wait for > > > events" we have lockdep annotation, but it is rather awkward to implement. > > > Having something that says "lockdep_wait_event()" and > > > "lockdep_exec_event()" wrappers would be useful. > > > > Yes. It's a problem of lack of APIs. It can be done by reverting revert > > of cross-release without big change. ;-) > > +1 on lockdep-native support for this. For another use case I've added > annotations for dma_fence_wait, and they're not entirely correct > unfortunately. But the false positives is along the lines of "you I'd like to help you solve the problem you are facing. Let me be back and help you later. I have to all-stop what I'm doing at the moment becasue of a very big personal issue, which is a sad thing. Thank you, Byungchul > really shouldn't do this, even if it's in theory deadlock free". See > > commit 5fbff813a4a328b730cb117027c43a4ae9d8b6c0 > Author: Daniel Vetter > Date: Tue Jul 7 22:12:05 2020 +0200 > >dma-fence: basic lockdep annotations > > for fairly lengthy discussion of the problem and what I ended up with. > > Thanks, Daniel > -- > Daniel Vetter > Software Engineer, Intel Corporation > http://blog.ffwll.ch
Re: [RFC] Are you good with Lockdep?
On Thu, Nov 12, 2020 at 11:28 PM Steven Rostedt wrote: > > On Thu, 12 Nov 2020 17:10:30 +0900 > Byungchul Park wrote: > > > 2. Does Lockdep do what a deadlock detection tool should do? From > >internal engine to APIs, all the internal data structure and > >algotithm of Lockdep is only looking at lock(?) acquisition order. > >Fundamentally Lockdep cannot work correctly with all general cases, > >for example, read/write/trylock and any wait/event. > > But lockdep does handle read/write/trylock and can handle wait/event (just > needs better wrappers to annotate this). Perhaps part of the confusion here > is that we believe that lockdep already does what you are asking for. > > > > >This can be done by re-introducing cross-release but still partially. > >A deadlock detector tool should thoroughly focus on *waits* and > >*events* to be more perfect at detecting deadlock because the fact is > >*waits* and their *events* that never reach cause deadlock. > > > >With the philosophy of Lockdep, we can only handle partial cases > >fundamently. We have no choice but to do various work-around or adopt > >tricky ways to cover more cases if we keep using Lockdep. > > > > > That said, I'm not at all interested in a wholesale replacement of > > > lockdep which will take exactly the same amount of time to stabilize and > > > weed out the shortcomings again. > > > > I don't want to bother ones who don't want to be bothered from the tool. > > But I think some day we need a new tool doing exactly what it should do > > for deadlock detection for sure. > > > > I'm willing to make it matured on my own, or with ones who need a > > stronger tool or willing to make it matured together - I wish tho. > > That's why I suggest to make both there until the new tool gets > > considered stable. > > > > FYI, roughly Lockdep is doing: > > > >1. Dependency check > >2. Lock usage correctness check (including RCU) > >3. IRQ related usage correctness check with IRQFLAGS > > > > 2 and 3 should be there forever which is subtle and have gotten matured. > > But 1 is not. I've been talking about 1. But again, it's not about > > replacing it right away but having both for a while. I'm gonna try my > > best to make it better. > > And I believe lockdep does handle 1. Perhaps show some tangible use case > that you want to cover that you do not believe that lockdep can handle. If > lockdep cannot handle it, it will show us where lockdep is lacking. If it > can handle it, it will educate you on other ways that lockdep can be > helpful in your development ;-) Yes. That's the best thing I can do for all of us. I will. I already did exactly the same thing while I was developing cross-release. But I'm willing to do it again with the current Lockdep code. But not today. It's over mid-night. Good night~ -- Thanks, Byungchul
Re: [RFC] Are you good with Lockdep?
On Thu, Nov 12, 2020 at 09:26:12AM -0500, Steven Rostedt wrote: > > FYI, roughly Lockdep is doing: > > > >1. Dependency check > >2. Lock usage correctness check (including RCU) > >3. IRQ related usage correctness check with IRQFLAGS > > > > 2 and 3 should be there forever which is subtle and have gotten matured. > > But 1 is not. I've been talking about 1. But again, it's not about > > replacing it right away but having both for a while. I'm gonna try my > > best to make it better. > > And I believe lockdep does handle 1. Perhaps show some tangible use case > that you want to cover that you do not believe that lockdep can handle. If > lockdep cannot handle it, it will show us where lockdep is lacking. If it > can handle it, it will educate you on other ways that lockdep can be > helpful in your development ;-) Something I believe lockdep is missing is a way to annotate "This lock will be released by a softirq". If we had lockdep for lock_page(), this would be a great case to show off. The filesystem locks the page, then submits it to a device driver. On completion, the filesystem's bio completion handler will be called in softirq context and unlock the page. So if the filesystem has another lock which is acquired by the completion handler. we could get an ABBA deadlock that lockdep would be unable to see. There are other similar things; if you look at the remaining semaphore users in the kernel, you'll see the general pattern is that they're acquired in process context and then released in interrupt context. If we had a way to transfer ownership of the semaphore to a generic "interrupt context", they could become mutexes and lockdep could check that nothing else will cause a deadlock.
Re: [RFC] Are you good with Lockdep?
On Thu, 12 Nov 2020 17:10:30 +0900 Byungchul Park wrote: > 2. Does Lockdep do what a deadlock detection tool should do? From >internal engine to APIs, all the internal data structure and >algotithm of Lockdep is only looking at lock(?) acquisition order. >Fundamentally Lockdep cannot work correctly with all general cases, >for example, read/write/trylock and any wait/event. But lockdep does handle read/write/trylock and can handle wait/event (just needs better wrappers to annotate this). Perhaps part of the confusion here is that we believe that lockdep already does what you are asking for. > >This can be done by re-introducing cross-release but still partially. >A deadlock detector tool should thoroughly focus on *waits* and >*events* to be more perfect at detecting deadlock because the fact is >*waits* and their *events* that never reach cause deadlock. > >With the philosophy of Lockdep, we can only handle partial cases >fundamently. We have no choice but to do various work-around or adopt >tricky ways to cover more cases if we keep using Lockdep. > > > That said, I'm not at all interested in a wholesale replacement of > > lockdep which will take exactly the same amount of time to stabilize and > > weed out the shortcomings again. > > I don't want to bother ones who don't want to be bothered from the tool. > But I think some day we need a new tool doing exactly what it should do > for deadlock detection for sure. > > I'm willing to make it matured on my own, or with ones who need a > stronger tool or willing to make it matured together - I wish tho. > That's why I suggest to make both there until the new tool gets > considered stable. > > FYI, roughly Lockdep is doing: > >1. Dependency check >2. Lock usage correctness check (including RCU) >3. IRQ related usage correctness check with IRQFLAGS > > 2 and 3 should be there forever which is subtle and have gotten matured. > But 1 is not. I've been talking about 1. But again, it's not about > replacing it right away but having both for a while. I'm gonna try my > best to make it better. And I believe lockdep does handle 1. Perhaps show some tangible use case that you want to cover that you do not believe that lockdep can handle. If lockdep cannot handle it, it will show us where lockdep is lacking. If it can handle it, it will educate you on other ways that lockdep can be helpful in your development ;-) -- Steve
Re: [RFC] Are you good with Lockdep?
On Thu, Nov 12, 2020 at 11:33 AM Byungchul Park wrote: > > On Wed, Nov 11, 2020 at 09:36:09AM -0500, Steven Rostedt wrote: > > And this is especially true with lockdep, because lockdep only detects the > > deadlock, it doesn't tell you which lock was the incorrect locking. > > > > For example. If we have a locking chain of: > > > > A -> B -> D > > > > A -> C -> D > > > > Which on a correct system looks like this: > > > > lock(A) > > lock(B) > > unlock(B) > > unlock(A) > > > > lock(B) > > lock(D) > > unlock(D) > > unlock(B) > > > > lock(A) > > lock(C) > > unlock(C) > > unlock(A) > > > > lock(C) > > lock(D) > > unlock(D) > > unlock(C) > > > > which creates the above chains in that order. > > > > But, lets say we have a bug and the system boots up doing: > > > > lock(D) > > lock(A) > > unlock(A) > > unlock(D) > > > > which creates the incorrect chain. > > > > D -> A > > > > > > Now you do the correct locking: > > > > lock(A) > > lock(B) > > > > Creates A -> B > > > > lock(A) > > lock(C) > > > > Creates A -> C > > > > lock(B) > > lock(D) > > > > Creates B -> D and lockdep detects: > > > > D -> A -> B -> D > > > > and gives us the lockdep splat!!! > > > > But we don't disable lockdep. We let it continue... > > > > lock(C) > > lock(D) > > > > Which creates C -> D > > > > Now it explodes with D -> A -> C -> D > > It would be better to check both so that we can choose either > breaking a single D -> A chain or both breaking A -> B -> D and > A -> C -> D. > > > Which it already reported. And it can be much more complex when dealing > > with interrupt contexts and longer chains. That is, perhaps a different > > IRQ context is much much worse than longer chains. I understand what you > try to explain. > > > chain had a missing irq disable, now you might get 5 or 6 more lockdep > > splats because of that one bug. > > > > The point I'm making is that the lockdep splats after the first one may > > just be another version of the same bug and not a new one. Worse, if you > > only look at the later lockdep splats, it may be much more difficult to > > find the original bug than if you just had the first one. Believe me, I've > > If the later lockdep splats make us more difficult to fix, then we can > look at the first one. If it's more informative, then we can check the > all splats. Anyway it's up to us. > > > been down that road too many times! > > > > And it can be very difficult to know if new lockdep splats are not the same > > bug, and this will waste a lot of developers time! > > Again, we don't have to waste time. We can go with the first one. > > > This is why the decision to disable lockdep after the first splat was made. > > There were times I wanted to check locking somewhere, but is was using > > linux-next which had a lockdep splat that I didn't care about. So I > > made it not disable lockdep. And then I hit this exact scenario, that the > > one incorrect chain was causing reports all over the place. To solve it, I > > had to patch the incorrect chain to do raw locking to have lockdep ignore > > it ;-) Then I was able to test the code I was interested in. > > It's not a problem of whether it's single-reporting or multi-reporting > but it's the problem of the lock creating the incorrect chain and making > you felt hard to handle. > > Even if you were using single-reporting Lockdep, you anyway had to > continue to ignore locks in the same way until you got to the intest. > > > I think I understand it. For things like completions and other "wait for > > events" we have lockdep annotation, but it is rather awkward to implement. > > Having something that says "lockdep_wait_event()" and > > "lockdep_exec_event()" wrappers would be useful. > > Yes. It's a problem of lack of APIs. It can be done by reverting revert > of cross-release without big change. ;-) +1 on lockdep-native support for this. For another use case I've added annotations for dma_fence_wait, and they're not entirely correct unfortunately. But the false positives is along the lines of "you really shouldn't do this, even if it's in theory deadlock free". See commit 5fbff813a4a328b730cb117027c43a4ae9d8b6c0 Author: Daniel Vetter Date: Tue Jul 7 22:12:05 2020 +0200 dma-fence: basic lockdep annotations for fairly lengthy discussion of the problem and what I ended up with. Thanks, Daniel -- Daniel Vetter Software Engineer, Intel Corporation http://blog.ffwll.ch
Re: [RFC] Are you good with Lockdep?
On Wed, Nov 11, 2020 at 09:36:09AM -0500, Steven Rostedt wrote: > And this is especially true with lockdep, because lockdep only detects the > deadlock, it doesn't tell you which lock was the incorrect locking. > > For example. If we have a locking chain of: > > A -> B -> D > > A -> C -> D > > Which on a correct system looks like this: > > lock(A) > lock(B) > unlock(B) > unlock(A) > > lock(B) > lock(D) > unlock(D) > unlock(B) > > lock(A) > lock(C) > unlock(C) > unlock(A) > > lock(C) > lock(D) > unlock(D) > unlock(C) > > which creates the above chains in that order. > > But, lets say we have a bug and the system boots up doing: > > lock(D) > lock(A) > unlock(A) > unlock(D) > > which creates the incorrect chain. > > D -> A > > > Now you do the correct locking: > > lock(A) > lock(B) > > Creates A -> B > > lock(A) > lock(C) > > Creates A -> C > > lock(B) > lock(D) > > Creates B -> D and lockdep detects: > > D -> A -> B -> D > > and gives us the lockdep splat!!! > > But we don't disable lockdep. We let it continue... > > lock(C) > lock(D) > > Which creates C -> D > > Now it explodes with D -> A -> C -> D It would be better to check both so that we can choose either breaking a single D -> A chain or both breaking A -> B -> D and A -> C -> D. > Which it already reported. And it can be much more complex when dealing > with interrupt contexts and longer chains. That is, perhaps a different IRQ context is much much worse than longer chains. I understand what you try to explain. > chain had a missing irq disable, now you might get 5 or 6 more lockdep > splats because of that one bug. > > The point I'm making is that the lockdep splats after the first one may > just be another version of the same bug and not a new one. Worse, if you > only look at the later lockdep splats, it may be much more difficult to > find the original bug than if you just had the first one. Believe me, I've If the later lockdep splats make us more difficult to fix, then we can look at the first one. If it's more informative, then we can check the all splats. Anyway it's up to us. > been down that road too many times! > > And it can be very difficult to know if new lockdep splats are not the same > bug, and this will waste a lot of developers time! Again, we don't have to waste time. We can go with the first one. > This is why the decision to disable lockdep after the first splat was made. > There were times I wanted to check locking somewhere, but is was using > linux-next which had a lockdep splat that I didn't care about. So I > made it not disable lockdep. And then I hit this exact scenario, that the > one incorrect chain was causing reports all over the place. To solve it, I > had to patch the incorrect chain to do raw locking to have lockdep ignore > it ;-) Then I was able to test the code I was interested in. It's not a problem of whether it's single-reporting or multi-reporting but it's the problem of the lock creating the incorrect chain and making you felt hard to handle. Even if you were using single-reporting Lockdep, you anyway had to continue to ignore locks in the same way until you got to the intest. > I think I understand it. For things like completions and other "wait for > events" we have lockdep annotation, but it is rather awkward to implement. > Having something that says "lockdep_wait_event()" and > "lockdep_exec_event()" wrappers would be useful. Yes. It's a problem of lack of APIs. It can be done by reverting revert of cross-release without big change. ;-) Thanks, Byungchul
Re: [RFC] Are you good with Lockdep?
On Thu, Nov 12, 2020 at 05:51:14PM +0900, Byungchul Park wrote: > On Thu, Nov 12, 2020 at 03:15:32PM +0900, Byungchul Park wrote: > > > If on the other hand there's some bug in lockdep itself that causes > > > excessive false positives, it's better to limit the number of reports > > > to one per bootup, so that it's not seen as a nuisance debugging > > > facility. > > > > > > Or if lockdep gets extended that causes multiple previously unreported > > > (but very much real) bugs to be reported, it's *still* better to > > > handle them one by one: because lockdep doesn't know whether it's real > > > > Why do you think we cannot handle them one by one with multi-reporting? > > We can handle them with the first one as we do with single-reporting. > > And also that's how we work, for example, when building the kernel or > > somethinig. > > Let me add a little bit more. I just said the fact that we are able to > handle the bugs one by one as if we do with single-reporting. > > But the thing is multi-reporting could be more useful in some cases. > More precisely speaking, bugs not caused by IRQ state will be reported > without annoying nuisance. I bet you have experienced a ton of nuisances > when multi-reporting Lockdep detected a deadlock by IRQ state. Last, we should never use multi-reporting Lockdep if Lockdep works like the current code because redundant warnings caused by IRQ state would be reported almost infinite times. I'm afraid you were talking about it. Thanks, Byungchul > For some cases, multi-reporting is as useful as single-reporting, while > for the other cases, multi-reporting is more useful. Then I think we > have to go with mutil-reporting if there's no technical issue. > > Thanks, > Byungchul
Re: [RFC] Are you good with Lockdep?
On Thu, Nov 12, 2020 at 03:15:32PM +0900, Byungchul Park wrote: > > If on the other hand there's some bug in lockdep itself that causes > > excessive false positives, it's better to limit the number of reports > > to one per bootup, so that it's not seen as a nuisance debugging > > facility. > > > > Or if lockdep gets extended that causes multiple previously unreported > > (but very much real) bugs to be reported, it's *still* better to > > handle them one by one: because lockdep doesn't know whether it's real > > Why do you think we cannot handle them one by one with multi-reporting? > We can handle them with the first one as we do with single-reporting. > And also that's how we work, for example, when building the kernel or > somethinig. Let me add a little bit more. I just said the fact that we are able to handle the bugs one by one as if we do with single-reporting. But the thing is multi-reporting could be more useful in some cases. More precisely speaking, bugs not caused by IRQ state will be reported without annoying nuisance. I bet you have experienced a ton of nuisances when multi-reporting Lockdep detected a deadlock by IRQ state. For some cases, multi-reporting is as useful as single-reporting, while for the other cases, multi-reporting is more useful. Then I think we have to go with mutil-reporting if there's no technical issue. Thanks, Byungchul
Re: [RFC] Are you good with Lockdep?
On Thu, Nov 12, 2020 at 12:16:50AM +0100, Thomas Gleixner wrote: > Wrappers which make things simpler are always useful, but the lack of > wrappers does not justify a wholesale replacement. Totally right. Lack of wrappers doesn't matter at all. That could be achieved easily by modifying the original e.i. Lockdep. That's why I didn't mention wrapper things in the description. (Sorry if I misled you so it looked like I mentioned just wrappers. I should've explained it in more detail.) xxx_wait(), xxx_event() and xxx_event_context_start() are much more than wrappers. It was about what deadlock detection tool should work based on. > We all know that lockdep has limitations but I yet have to see a proper > argument why this can't be solved incrementaly on top of the existing > infrastructure. This is exactly what I'd like to address. As you can see in the first mail, the reasons why this can't be solved incrementaly are: 1. Lockdep's design and implementation are too complicated to be generalized so as to allow multi-reporting. Quite big change onto Lockdep would be required. I think allowing multi-reporting is very important for tools like Lockdep. As long as false positive in the single-reporting manner bothers folks, tools like Lockdep cannot be enhanced so as to have stronger capability. 2. Does Lockdep do what a deadlock detection tool should do? From internal engine to APIs, all the internal data structure and algotithm of Lockdep is only looking at lock(?) acquisition order. Fundamentally Lockdep cannot work correctly with all general cases, for example, read/write/trylock and any wait/event. This can be done by re-introducing cross-release but still partially. A deadlock detector tool should thoroughly focus on *waits* and *events* to be more perfect at detecting deadlock because the fact is *waits* and their *events* that never reach cause deadlock. With the philosophy of Lockdep, we can only handle partial cases fundamently. We have no choice but to do various work-around or adopt tricky ways to cover more cases if we keep using Lockdep. > That said, I'm not at all interested in a wholesale replacement of > lockdep which will take exactly the same amount of time to stabilize and > weed out the shortcomings again. I don't want to bother ones who don't want to be bothered from the tool. But I think some day we need a new tool doing exactly what it should do for deadlock detection for sure. I'm willing to make it matured on my own, or with ones who need a stronger tool or willing to make it matured together - I wish tho. That's why I suggest to make both there until the new tool gets considered stable. FYI, roughly Lockdep is doing: 1. Dependency check 2. Lock usage correctness check (including RCU) 3. IRQ related usage correctness check with IRQFLAGS 2 and 3 should be there forever which is subtle and have gotten matured. But 1 is not. I've been talking about 1. But again, it's not about replacing it right away but having both for a while. I'm gonna try my best to make it better. Thanks, Byungchul
Re: [RFC] Are you good with Lockdep?
On Wed, Nov 11, 2020 at 11:54:41AM +0100, Ingo Molnar wrote: > > We cannot get reported other than the first one. > > Correct. Experience has shown that the overwhelming majority of > lockdep reports are single-cause and single-report. > > This is an optimal approach, because after a decade of exorcising > locking bugs from the kernel, lockdep is currently, most of the time, I also think Lockdep has been doing great job exorcising almost all locking bugs so far. Respect it. > in 'steady-state', with there being no reports for the overwhelming > majority of testcases, so the statistical probability of there being > just one new report is by far the highest. This is true if Lockdep is only for checking if maintainers' tree are ok and if we totally ignore how a tool could help folks in the middle of development esp. when developing something complicated wrt. synchronization. But I don't agree if a tool could help while developing something that could introduce many dependency issues. > If on the other hand there's some bug in lockdep itself that causes > excessive false positives, it's better to limit the number of reports > to one per bootup, so that it's not seen as a nuisance debugging > facility. > > Or if lockdep gets extended that causes multiple previously unreported > (but very much real) bugs to be reported, it's *still* better to > handle them one by one: because lockdep doesn't know whether it's real Why do you think we cannot handle them one by one with multi-reporting? We can handle them with the first one as we do with single-reporting. And also that's how we work, for example, when building the kernel or somethinig. > >So the one who has introduced the first one should fix it as soon > >as possible so that the other problems can be reported and fixed. > >It will get even worse if it's a false positive because it's > >worth nothing but only preventing reporting real ones. > > Since kernel development is highly distributed, and 90%+ of new > commits get created in dozens of bigger and hundreds of smaller > maintainer topic trees, the chance of getting two independent locking > bugs in the same tree without the first bug being found & fixed is > actually pretty low. Again, this is true if Lockdep is for checking maintainers' tree only. > linux-next offers several weeks/months advance integration testing to > see whether the combination of maintainer trees causes > problems/warnings. Good for us. > >That's why kernel developers are so sensitive to Lockdep's false > >positive reporting - I would, too. But precisely speaking, it's a > >problem of how Lockdep was designed and implemented, not false > >positive itself. Annoying false positives - as WARN()'s messages are > >annoying - should be fixed but we don't have to be as sensitive as we > >are now if the tool keeps normally working even after reporting. > > I disagree, and even for WARN()s we are seeing a steady movement > towards WARN_ON_ONCE(): exactly because developers are usually > interested in the first warning primarily. > > Followup warnings are even marked 'tainted' by the kernel - if a bug > happened we cannot trust the state of the kernel anymore, even if it > seems otherwise functional. This is doubly true for lockdep, where I definitely think so. Already tainted kernel is not the kernel we can trust anymore. Again, IMO, a tool should help us not only for checking almost final trees but also in developing something. No? > But for lockdep there's another concern: we do occasionally report > bugs in locking facilities themselves. In that case it's imperative > for all lockdep activity to cease & desist, so that we are able to get > a log entry out before the kernel goes down potentially. Sure. Makes sense. > I.e. there's a "race to log the bug as quickly as possible", which is > the other reason we shut down lockdep immediately. But once shut down, Not sure I understand this part. > all the lockdep data structures are hopelessly out of sync and it > cannot be restarted reasonably. Is it about tracking IRQ and IRQ-enabled state? That's exactly what I'd like to point out. Or is there something else? > Not sure I understand the "problem 2)" outlined here, but I'm looking > forward to your patchset! Thank you for the response. Thanks, Byungchul
Re: [RFC] Are you good with Lockdep?
On Wed, Nov 11 2020 at 09:36, Steven Rostedt wrote: > Ingo Molnar wrote: >> Not sure I understand the "problem 2)" outlined here, but I'm looking >> forward to your patchset! >> > I think I understand it. For things like completions and other "wait for > events" we have lockdep annotation, but it is rather awkward to implement. > Having something that says "lockdep_wait_event()" and > "lockdep_exec_event()" wrappers would be useful. Wrappers which make things simpler are always useful, but the lack of wrappers does not justify a wholesale replacement. We all know that lockdep has limitations but I yet have to see a proper argument why this can't be solved incrementaly on top of the existing infrastructure. That said, I'm not at all interested in a wholesale replacement of lockdep which will take exactly the same amount of time to stabilize and weed out the shortcomings again. Thanks, tglx
Re: [RFC] Are you good with Lockdep?
On Wed, 11 Nov 2020 11:54:41 +0100 Ingo Molnar wrote: > * Byungchul Park wrote: > > > PROBLEM 1) First of all, Lockdep gets disabled on the first detection. > > Lockdep disabling itself after the first warning was an intentional > and deliberate design decision. (See more details below.) > [..] > Making the code simpler is always welcome, but I disagree with > enabling multiple warnings, for the technical reasons outlined above. I 100% agree with Ingo. I wish we could stop *all* warnings after the first one. The number of times people sent me bug reports with warnings without showing me previous warnings that caused me to go on wild goose chases is too many to count. The first warning is the *only* thing I look at. Anything after that is likely to be caused by the integrity of the system being compromised by the first bug. And this is especially true with lockdep, because lockdep only detects the deadlock, it doesn't tell you which lock was the incorrect locking. For example. If we have a locking chain of: A -> B -> D A -> C -> D Which on a correct system looks like this: lock(A) lock(B) unlock(B) unlock(A) lock(B) lock(D) unlock(D) unlock(B) lock(A) lock(C) unlock(C) unlock(A) lock(C) lock(D) unlock(D) unlock(C) which creates the above chains in that order. But, lets say we have a bug and the system boots up doing: lock(D) lock(A) unlock(A) unlock(D) which creates the incorrect chain. D -> A Now you do the correct locking: lock(A) lock(B) Creates A -> B lock(A) lock(C) Creates A -> C lock(B) lock(D) Creates B -> D and lockdep detects: D -> A -> B -> D and gives us the lockdep splat!!! But we don't disable lockdep. We let it continue... lock(C) lock(D) Which creates C -> D Now it explodes with D -> A -> C -> D Which it already reported. And it can be much more complex when dealing with interrupt contexts and longer chains. That is, perhaps a different chain had a missing irq disable, now you might get 5 or 6 more lockdep splats because of that one bug. The point I'm making is that the lockdep splats after the first one may just be another version of the same bug and not a new one. Worse, if you only look at the later lockdep splats, it may be much more difficult to find the original bug than if you just had the first one. Believe me, I've been down that road too many times! And it can be very difficult to know if new lockdep splats are not the same bug, and this will waste a lot of developers time! This is why the decision to disable lockdep after the first splat was made. There were times I wanted to check locking somewhere, but is was using linux-next which had a lockdep splat that I didn't care about. So I made it not disable lockdep. And then I hit this exact scenario, that the one incorrect chain was causing reports all over the place. To solve it, I had to patch the incorrect chain to do raw locking to have lockdep ignore it ;-) Then I was able to test the code I was interested in. > > > PROBLEM 2) Lockdep forces us to emulate lock acquisition for non-lock. > > >I have the patch set. Let me share it with you in a few days. > > Not sure I understand the "problem 2)" outlined here, but I'm looking > forward to your patchset! > I think I understand it. For things like completions and other "wait for events" we have lockdep annotation, but it is rather awkward to implement. Having something that says "lockdep_wait_event()" and "lockdep_exec_event()" wrappers would be useful. -- Steve
Re: [RFC] Are you good with Lockdep?
* Byungchul Park wrote: > PROBLEM 1) First of all, Lockdep gets disabled on the first detection. Lockdep disabling itself after the first warning was an intentional and deliberate design decision. (See more details below.) >What if there are more than two problems? So the usual way this happens is that the first reported bug gets discovered & fixed, then the second gets discovered & fixed. > We cannot get reported other than the first one. Correct. Experience has shown that the overwhelming majority of lockdep reports are single-cause and single-report. This is an optimal approach, because after a decade of exorcising locking bugs from the kernel, lockdep is currently, most of the time, in 'steady-state', with there being no reports for the overwhelming majority of testcases, so the statistical probability of there being just one new report is by far the highest. If on the other hand there's some bug in lockdep itself that causes excessive false positives, it's better to limit the number of reports to one per bootup, so that it's not seen as a nuisance debugging facility. Or if lockdep gets extended that causes multiple previously unreported (but very much real) bugs to be reported, it's *still* better to handle them one by one: because lockdep doesn't know whether it's real or a nuisance, and also because of the "race to log" reasoning below. >So the one who has introduced the first one should fix it as soon >as possible so that the other problems can be reported and fixed. >It will get even worse if it's a false positive because it's >worth nothing but only preventing reporting real ones. Since kernel development is highly distributed, and 90%+ of new commits get created in dozens of bigger and hundreds of smaller maintainer topic trees, the chance of getting two independent locking bugs in the same tree without the first bug being found & fixed is actually pretty low. linux-next offers several weeks/months advance integration testing to see whether the combination of maintainer trees causes problems/warnings. And if multiple locking bugs on top of each other happen regularly in a particular maintainer tree, it's probably not lockdep's fault. ;-) >That's why kernel developers are so sensitive to Lockdep's false >positive reporting - I would, too. But precisely speaking, it's a >problem of how Lockdep was designed and implemented, not false >positive itself. Annoying false positives - as WARN()'s messages are >annoying - should be fixed but we don't have to be as sensitive as we >are now if the tool keeps normally working even after reporting. I disagree, and even for WARN()s we are seeing a steady movement towards WARN_ON_ONCE(): exactly because developers are usually interested in the first warning primarily. Followup warnings are even marked 'tainted' by the kernel - if a bug happened we cannot trust the state of the kernel anymore, even if it seems otherwise functional. This is doubly true for lockdep, where locking state is complex because the kernel with its thousands of lock types and millions of lock instances is fundamentally & inescapably complex. The 'first warning' is by far the most valuable one - and this is what lockdep's "turn off after the first warning" policy implements. But for lockdep there's another concern: we do occasionally report bugs in locking facilities themselves. In that case it's imperative for all lockdep activity to cease & desist, so that we are able to get a log entry out before the kernel goes down potentially. I.e. there's a "race to log the bug as quickly as possible", which is the other reason we shut down lockdep immediately. But once shut down, all the lockdep data structures are hopelessly out of sync and it cannot be restarted reasonably. I.e. these are two independent reasons to shut down lockdep after the first problem found. >But it's very hard to achieve it with Lockdep because of the complex >design. Maybe re-designing and re-implementing almost whole code >would be required. Making the code simpler is always welcome, but I disagree with enabling multiple warnings, for the technical reasons outlined above. > PROBLEM 2) Lockdep forces us to emulate lock acquisition for non-lock. >I have the patch set. Let me share it with you in a few days. Not sure I understand the "problem 2)" outlined here, but I'm looking forward to your patchset! Thanks, Ingo
[RFC] Are you good with Lockdep?
Hello folks, We have no choise but to use Lockdep to track dependencies for deadlock detection with the current kernel. I'm wondering if they are satifsied in that tool. Lockdep has too big problems to continue to use. --- PROBLEM 1) First of all, Lockdep gets disabled on the first detection. What if there are more than two problems? We cannot get reported other than the first one. So the one who has introduced the first one should fix it as soon as possible so that the other problems can be reported and fixed. It will get even worse if it's a false positive because it's worth nothing but only preventing reporting real ones. That's why kernel developers are so sensitive to Lockdep's false positive reporting - I would, too. But precisely speaking, it's a problem of how Lockdep was designed and implemented, not false positive itself. Annoying false positives - as WARN()'s messages are annoying - should be fixed but we don't have to be as sensitive as we are now if the tool keeps normally working even after reporting. But it's very hard to achieve it with Lockdep because of the complex design. Maybe re-designing and re-implementing almost whole code would be required. PROBLEM 2) Lockdep forces us to emulate lock acquisition for non-lock. We add manual annotations for non-lock code in the following way: At the interest wait, ... lockdep_acquire(X); lockdep_release(X); wait_for_something(X); ... At begin and end of the region where we expect there's the something, ... lockdep_acquire(X); (or lockdep_acquire_read(); to allow recursive annotations.) function_doing_the_something(X); lockdep_release(X); ... This way we try to detect deadlocks by waits for now. But don't you think it looks ugly? Are you good if it manages to work by some means? That even doesn't work correctly. Instead it should look like: At the interest wait, ... xxx_wait(X); wait_for_something(X); ... At the something, ... xxx_event(X); do_the_something(X); ... Or at begin and end of the region for hint, ... xxx_event_context_enter(X); function_doing_the_something(X); xxx_event_context_exit(X); ... Lockdep had been a not bad tool for detecting deadlock by problematic acquisition order. But it's worth noting that deadlock is caused by *waits* and their *events* that never reach. Deadlock detection tool should focus on waits and events instead of lock acquisition order. Just FYI, it should look like for locks: At the interest lock acquisition, ... xxx_wait(X); xxx_event_context_enter(X); lock(X); ... At the lock acquisition using trylock type, ... xxx_event_context_enter(X); lock(X); ... At the lock release, ... xxx_event(X); xxx_event_context_exit(X); unlock(X); ... --- These two are big-why we should not keep using Lockdep as a deadlock detection tool. Other small things can be fixed by modifying Lockdep but these two are not. Fine. What could we do for it? Options that I've considered are: --- OPTION 1) Revert reverting cross-release locking checks (e966eaeeb62 locking/lockdep: Remove the cross-release locking checks) or implement another Lockdep extention like cross-release. The reason cross-release was reverted was a few false positives - someone was lying like there were too many false positives though - leading people to disable Lockdep. I admit it had to be done that way. Folks still don't like Lockdep's false positive that stops the tool. OPTION 2) Newally design and implement another tool for deadlock detection based on wait-event model. And replace Lockdep right away. Lockdep definitely includes all the efforts great developers have made for a long time as as to be quite stable enough. But the new one is not. It's not good idea to replace Lockdep right away. OPTION 3) Newally design and implement another tool for deadlock detection based on wait-event model. And keep both Lockdep and the new tool until the new one gets considered stable. For people who need stronger capacity for deadlock detection, the new tool needs to be introduced but de-coupled with Lockdep so as to be getting matured independently. I think this option is the best. I have the patch set. Let me share it with you in a few days. --- Thanks, Byungchul
