| Message ID | Y+gLd78vChQERZ6A@rowland.harvard.edu |
|---|---|
| State | New |
| Headers | show |
| Series | [RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys | expand |
On Sat, Feb 11, 2023 at 04:41:11PM -0500, Alan Stern wrote: > Lockdep is blind to the dev->mutex field of struct device, owing to > the fact that these mutexes are assigned to lockdep's "novalidate" > class. Commit 1704f47b50b5 ("lockdep: Add novalidate class for > dev->mutex conversion") did this because the hierarchical nature of > the device tree makes it impossible in practice to determine whether > acquiring one of these mutexes is safe or might lead to a deadlock. > > Unfortunately, this means that lockdep is unable to help diagnose real > deadlocks involving these mutexes when they occur in testing [1] [2] > or in actual use, or to detect bad locking patterns that might lead to > a deadlock. We would like to obtain as much of lockdep's benefits as > possible without generating a flood of false positives -- which is > what happens if one naively removes these mutexes from the > "novalidate" class. > > Accordingly, as a middle ground the mutex in each non-static struct > device will be placed in its own unique locking class. This approach > gives up some of lockdep's advantages (for example, all devices having > a particular bus_type or device_type might reasonably be put into the > same locking class), but it should at least allow us to gain the > benefit of some of lockdep's capabilities. > > Link: https://syzkaller.appspot.com/bug?extid=2d6ac90723742279e101 [1] > Link: https://syzkaller.appspot.com/bug?extid=2e39bc6569d281acbcfb [2] > Link: https://lore.kernel.org/all/28a82f50-39d5-a45f-7c7a-57a66cec0741@I-love.SAKURA.ne.jp/ > Suggested-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> > Signed-off-by: Alan Stern <stern@rowland.harvard.edu> > CC: Peter Zijlstra <peterz@infradead.org> > CC: Ingo Molnar <mingo@redhat.com> > CC: Boqun Feng <boqun.feng@gmail.com> My main worry when adding a ton of classes like this is the combinatorics (dynamic classes make this more trivial, but it's entirely possible with just static classes too). As an example, we used to have a static class per cpu runqueue, now, given migration takes two runqueue locks (per locking rules in cpu order -- source and dest runqueue etc..) we got O(n^2) combinations of class orderings, which lead to a giant graph, which led to both performance and memory usage issues.
On Mon, Feb 13, 2023 at 10:49:50AM +0100, Peter Zijlstra wrote: > My main worry when adding a ton of classes like this is the > combinatorics (dynamic classes make this more trivial, but it's entirely > possible with just static classes too). > > As an example, we used to have a static class per cpu runqueue, now, > given migration takes two runqueue locks (per locking rules in cpu > order -- source and dest runqueue etc..) we got O(n^2) combinations of > class orderings, which lead to a giant graph, which led to both > performance and memory usage issues. Having a new class for each device would add a lot of classes. Just how badly this would affect lockdep's performance is hard to predict. Testing seems like the best way to find out. > From this was born the subclass, which reduced the whole thing to a > static ordering of runqueue-1 goes inside runqueue-0. > > Similar combinatoric issues have cropped up in other places from time to > time, typically solved by using a different annotation. > > Now, given the whole device thing is more or less a tree, hierarchical > locking should limit that, the only worry is that sibling locking while > holding parent thing. If siblings are of different classes, things will > both complain and create combinatorics again. Actually, I expect the sibling ordering thing won't come up very often. If it does occur somewhere, there's an excellent chance it can be fixed by hand (always locking the children in the same order). I'm worried more about other things. Suppose do we manage somehow to tell lockdep about locks belonging to a logical tree structure. How can this be incorporated into the checking algorithm? Here's an example. Let A be a parent device and B its child, and let X be some other type of lock entirely (not a device lock). Suppose at some point in the distant past, a first thread locked B and then X -- both locks long since released. Now suppose a second thread locks A and then X (presumably valid, right?). What should happen if this thread tries to lock B? This ought to give rise to a violation: B->X and X->B. But would this not be checked, under the rule that holding A's lock makes it okay to take B's lock? For that matter, what if the second thread had locked X and then A. Should that be allowed? Even though it doesn't directly contradict B->X? Here's a more complicated example, taken from the USB subsystem. Each usb_device structure representing a hub has some number of children usb_device structures (for the USB devices plugged into the hub), as well as a bunch of child usb_port device structures (representing the hub's own downstream ports, which the other USB devices are plugged into). In theory the child usb_device should really be a direct child of the usb_port it's plugged into, but for historical reasons the two are siblings instead. So now we have a rule that you cannot lock a usb_device if you're holding the lock of the usb_port that it's plugged into. (Yes, this is logically backwards.) How could we get lockdep to check this? The only approach I can think of is something I suggested earlier in this discussion: Create lockdep classes for bus_types or device_types rather than for individual devices. (usb_device and usb_port have different device_types.) But I don't know how to combine this with the tree-structured approach. Alan Stern
On Mon, Feb 13, 2023 at 11:18:50AM -0500, Alan Stern wrote: > On Mon, Feb 13, 2023 at 10:49:50AM +0100, Peter Zijlstra wrote: > > My main worry when adding a ton of classes like this is the > > combinatorics (dynamic classes make this more trivial, but it's entirely > > possible with just static classes too). > > > > As an example, we used to have a static class per cpu runqueue, now, > > given migration takes two runqueue locks (per locking rules in cpu > > order -- source and dest runqueue etc..) we got O(n^2) combinations of > > class orderings, which lead to a giant graph, which led to both > > performance and memory usage issues. > > Having a new class for each device would add a lot of classes. Just how > badly this would affect lockdep's performance is hard to predict. > Testing seems like the best way to find out. We support systems with 50000+ devices today, so one class per device might be messy. But back to the original issue here, why any of this? What's wrong with what we have now? I haven't seen real locking issues reported yet (only odd syzbot reports that didn't make any sense.) Is this effort even worth it? thanks, greg k-h
Index: usb-devel/drivers/base/core.c =================================================================== --- usb-devel.orig/drivers/base/core.c +++ usb-devel/drivers/base/core.c @@ -2322,6 +2322,9 @@ static void device_release(struct kobjec devres_release_all(dev); kfree(dev->dma_range_map); + mutex_destroy(&dev->mutex); + if (!lockdep_static_obj(dev)) + lockdep_unregister_key(&dev->mutex_key); if (dev->release) dev->release(dev); @@ -2941,7 +2944,10 @@ void device_initialize(struct device *de kobject_init(&dev->kobj, &device_ktype); INIT_LIST_HEAD(&dev->dma_pools); mutex_init(&dev->mutex); - lockdep_set_novalidate_class(&dev->mutex); + if (!lockdep_static_obj(dev)) { + lockdep_register_key(&dev->mutex_key); + lockdep_set_class(&dev->mutex, &dev->mutex_key); + } spin_lock_init(&dev->devres_lock); INIT_LIST_HEAD(&dev->devres_head); device_pm_init(dev); Index: usb-devel/include/linux/device.h =================================================================== --- usb-devel.orig/include/linux/device.h +++ usb-devel/include/linux/device.h @@ -570,6 +570,7 @@ struct device { struct mutex mutex; /* mutex to synchronize calls to * its driver. */ + struct lock_class_key mutex_key; /* Unique key for each device */ struct dev_links_info links; struct dev_pm_info power; Index: usb-devel/include/linux/lockdep.h =================================================================== --- usb-devel.orig/include/linux/lockdep.h +++ usb-devel/include/linux/lockdep.h @@ -172,6 +172,7 @@ do { \ current->lockdep_recursion -= LOCKDEP_OFF; \ } while (0) +extern int lockdep_static_obj(const void *obj); extern void lockdep_register_key(struct lock_class_key *key); extern void lockdep_unregister_key(struct lock_class_key *key); @@ -391,6 +392,11 @@ static inline void lockdep_set_selftest_ # define lockdep_free_key_range(start, size) do { } while (0) # define lockdep_sys_exit() do { } while (0) +static inline int lockdep_static_obj(const void *obj) +{ + return 0; +} + static inline void lockdep_register_key(struct lock_class_key *key) { } Index: usb-devel/kernel/locking/lockdep.c =================================================================== --- usb-devel.orig/kernel/locking/lockdep.c +++ usb-devel/kernel/locking/lockdep.c @@ -857,6 +857,11 @@ static int static_obj(const void *obj) */ return is_module_address(addr) || is_module_percpu_address(addr); } + +int lockdep_static_obj(const void *obj) +{ + return static_obj(obj); +} #endif /*
Lockdep is blind to the dev->mutex field of struct device, owing to the fact that these mutexes are assigned to lockdep's "novalidate" class. Commit 1704f47b50b5 ("lockdep: Add novalidate class for dev->mutex conversion") did this because the hierarchical nature of the device tree makes it impossible in practice to determine whether acquiring one of these mutexes is safe or might lead to a deadlock. Unfortunately, this means that lockdep is unable to help diagnose real deadlocks involving these mutexes when they occur in testing [1] [2] or in actual use, or to detect bad locking patterns that might lead to a deadlock. We would like to obtain as much of lockdep's benefits as possible without generating a flood of false positives -- which is what happens if one naively removes these mutexes from the "novalidate" class. Accordingly, as a middle ground the mutex in each non-static struct device will be placed in its own unique locking class. This approach gives up some of lockdep's advantages (for example, all devices having a particular bus_type or device_type might reasonably be put into the same locking class), but it should at least allow us to gain the benefit of some of lockdep's capabilities. Link: https://syzkaller.appspot.com/bug?extid=2d6ac90723742279e101 [1] Link: https://syzkaller.appspot.com/bug?extid=2e39bc6569d281acbcfb [2] Link: https://lore.kernel.org/all/28a82f50-39d5-a45f-7c7a-57a66cec0741@I-love.SAKURA.ne.jp/ Suggested-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> Signed-off-by: Alan Stern <stern@rowland.harvard.edu> CC: Peter Zijlstra <peterz@infradead.org> CC: Ingo Molnar <mingo@redhat.com> CC: Boqun Feng <boqun.feng@gmail.com> --- I decided to take your suggestion about introducing a new lockdep_static_obj() function, to reduce the size of the patch. It can always be combined with the original static_obj() function later on, if that's what the lockdep developers want. If Hillf Danton contributed any of the code for this patch, I haven't seen it in any messages sent to me or in the mailing list archives. That's why I didn't include a Co-developed-by: tag for him. drivers/base/core.c | 8 +++++++- include/linux/device.h | 1 + include/linux/lockdep.h | 6 ++++++ kernel/locking/lockdep.c | 5 +++++ 4 files changed, 19 insertions(+), 1 deletion(-)