Converting dev->mutex into dev->spinlock ?

Converting dev->mutex into dev->spinlock ?

[Tetsuo Handa]

Hello.

There is a long-standing deadlock problem in driver core code caused by
"struct device"->mutex being marked as "do not apply lockdep checks".

We can make this deadlock visible by applying [1], and we can confirm that
there is a deadlock problem that I think needs to be addressed in core code [2].

Also, since driver developers are taking it for granted that driver callback
functions can behave as if dev->mutex is not held (because possibility of deadlock
was never reported), it would solve many deadlocks in driver code if you can update
driver core code to avoid calling driver callback functions with dev->mutex held
(by e.g. replacing dev->mutex with dev->spinlock and dev->atomic_flags).
But I'm not familiar enough to propose such change...

[1] https://lkml.kernel.org/r/8c3fc3d1-8fed-be22-e0e7-ef1e1ea723ce@I-love.SAKURA.ne.jp
[2] https://lkml.kernel.org/r/b7bc63c8-bb28-d21d-7c3f-97e4e79a9292@I-love.SAKURA.ne.jp

Re: Converting dev->mutex into dev->spinlock ?

[Greg Kroah-Hartman]

On Sat, Feb 04, 2023 at 10:32:11PM +0900, Tetsuo Handa wrote:
> Hello.
> 
> There is a long-standing deadlock problem in driver core code caused by
> "struct device"->mutex being marked as "do not apply lockdep checks".

The marking of a lock does not cause a deadlock problem, so what do you
mean exactly by this?  Where is the actual deadlock?

> We can make this deadlock visible by applying [1], and we can confirm that
> there is a deadlock problem that I think needs to be addressed in core code [2].

Any reason why you didn't cc: us on these patches?

> Also, since driver developers are taking it for granted that driver callback
> functions can behave as if dev->mutex is not held (because possibility of deadlock
> was never reported), it would solve many deadlocks in driver code if you can update
> driver core code to avoid calling driver callback functions with dev->mutex held
> (by e.g. replacing dev->mutex with dev->spinlock and dev->atomic_flags).
> But I'm not familiar enough to propose such change...

A driver developer should never be messing with the mutex of a device,
that's not for them to touch, that's the driver core's lock to touch,
right?

So I don't understand the real problem here.  What subsystem is having
issues and what issues are they exactly?

And using a spinlock shouldn't change any locking deadlocks that I can
tell, so I don't understand the proposal, sorry.

thanks,

greg k-h

Re: Converting dev->mutex into dev->spinlock ?

[Tetsuo Handa]

On 2023/02/04 22:47, Greg Kroah-Hartman wrote:
> On Sat, Feb 04, 2023 at 10:32:11PM +0900, Tetsuo Handa wrote:
>> Hello.
>>
>> There is a long-standing deadlock problem in driver core code caused by
>> "struct device"->mutex being marked as "do not apply lockdep checks".
> 
> The marking of a lock does not cause a deadlock problem, so what do you
> mean exactly by this?  Where is the actual deadlock?

A few of examples:

  https://syzkaller.appspot.com/bug?extid=2d6ac90723742279e101
  https://syzkaller.appspot.com/bug?extid=2e39bc6569d281acbcfb
  https://syzkaller.appspot.com/bug?extid=9ef743bba3a17c756174

> 
>> We can make this deadlock visible by applying [1], and we can confirm that
>> there is a deadlock problem that I think needs to be addressed in core code [2].
> 
> Any reason why you didn't cc: us on these patches?

We can't apply this "drivers/core: Remove lockdep_set_novalidate_class() usage" patch
until we fix all lockdep warnings that happen during the boot stage; otherwise syzbot
testing can't work which is more painful than applying this patch now.

Therefore, I locally tested this patch (in order not to be applied now). And I got
a lockdep warning on the perf_event code. I got next lockdep warning on the driver core
code when I tried a fix for the perf_event code suggested by Peter Zijlstra. Since Peter
confirmed that this is a problem that led to commit 1704f47b50b5 ("lockdep: Add novalidate
class for dev->mutex conversion"), this time I'm reporting this problem to you (so that
you can propose a fix for the driver core code).

Re: Converting dev->mutex into dev->spinlock ?

[Greg Kroah-Hartman]

On Sat, Feb 04, 2023 at 11:21:27PM +0900, Tetsuo Handa wrote:
> On 2023/02/04 22:47, Greg Kroah-Hartman wrote:
> > On Sat, Feb 04, 2023 at 10:32:11PM +0900, Tetsuo Handa wrote:
> >> Hello.
> >>
> >> There is a long-standing deadlock problem in driver core code caused by
> >> "struct device"->mutex being marked as "do not apply lockdep checks".
> > 
> > The marking of a lock does not cause a deadlock problem, so what do you
> > mean exactly by this?  Where is the actual deadlock?
> 
> A few of examples:
> 
>   https://syzkaller.appspot.com/bug?extid=2d6ac90723742279e101
>   https://syzkaller.appspot.com/bug?extid=2e39bc6569d281acbcfb
>   https://syzkaller.appspot.com/bug?extid=9ef743bba3a17c756174

Random links to syzkaller reports that are huge and not descriptive does
not actually persuade me as I don't have the inclination to dig through
them, sorry.

Specific examples, with code, please.

> >> We can make this deadlock visible by applying [1], and we can confirm that
> >> there is a deadlock problem that I think needs to be addressed in core code [2].
> > 
> > Any reason why you didn't cc: us on these patches?
> 
> We can't apply this "drivers/core: Remove lockdep_set_novalidate_class() usage" patch

What patch is that?  I do not see that in my inbox anywhere.  I don't
even see it in my lkml archive, so I do not know what you are talking
about.

> until we fix all lockdep warnings that happen during the boot stage;

What lockdep warnings?

> otherwise syzbot testing can't work which is more painful than
> applying this patch now.

Again, I'm totally confused.  What is the real bug/problem/issue here?

Where is the deadlock?

> Therefore, I locally tested this patch (in order not to be applied now).

What patch?  I'm totally confused.

> And I got a lockdep warning on the perf_event code.

What warning?

> I got next lockdep warning on the driver core code when I tried a fix
> for the perf_event code suggested by Peter Zijlstra.

Again, what warning?

> Since Peter confirmed that this is a problem that led to commit
> 1704f47b50b5 ("lockdep: Add novalidate class for dev->mutex
> conversion"), this time I'm reporting this problem to you (so that you
> can propose a fix for the driver core code).

Again, I have no idea what the real problem is!

Please show me in the driver core code, where the deadlock is that needs
to be resolved.  Without that, I can't answer anything...

totally and throughly confused,

greg k-h

Re: Converting dev->mutex into dev->spinlock ?

[Alan Stern]

On Sat, Feb 04, 2023 at 10:32:11PM +0900, Tetsuo Handa wrote:
> Hello.
> 
> There is a long-standing deadlock problem in driver core code caused by
> "struct device"->mutex being marked as "do not apply lockdep checks".

What exactly is the deadlock problem?  Furthermore, how can skipping 
some lockdep checks _cause_ a problem?

> We can make this deadlock visible by applying [1], and we can confirm that
> there is a deadlock problem that I think needs to be addressed in core code [2].

I don't understand why you think there is a deadlock problem.  The splat 
in [2] says "WARNING: possible recursive locking detected".  This is 
only a warning; it doesn't mean there really is a problem.

> Also, since driver developers are taking it for granted that driver callback
> functions can behave as if dev->mutex is not held (because possibility of deadlock
> was never reported),

What?  I have no idea what developers you're talking about.  I have 
never heard of anyone taking this for granted.  Certainly developers 
working on the USB subsystem's core are well aware of dev->mutex 
locking.

>  it would solve many deadlocks in driver code if you can update

What deadlocks?  If there are so many deadlocks floating around in 
driver code, why haven't we heard about them before now?

> driver core code to avoid calling driver callback functions with dev->mutex held

We most definitely cannot do that.  The driver core relies on mutual 
exclusion.

> (by e.g. replacing dev->mutex with dev->spinlock and dev->atomic_flags).
> But I'm not familiar enough to propose such change...

Such a change cannot be made.  Consider this: Driver callbacks often
need to sleep.  But when a thread holds a spinlock, it is not allowed to 
sleep.  Therefore driver callbacks must not be invoked while a spinlock 
is held.

Besides, how will replacing a mutex with a spinlock prevent any deadlock 
problems?  If the new locks get held at the same time as the old mutexes 
were held, won't the same deadlocks occur?

Alan Stern

> [1] https://lkml.kernel.org/r/8c3fc3d1-8fed-be22-e0e7-ef1e1ea723ce@I-love.SAKURA.ne.jp
> [2] https://lkml.kernel.org/r/b7bc63c8-bb28-d21d-7c3f-97e4e79a9292@I-love.SAKURA.ne.jp

Re: Converting dev->mutex into dev->spinlock ?

[Tetsuo Handa]

On 2023/02/04 23:34, Greg Kroah-Hartman wrote:
>>>> We can make this deadlock visible by applying [1], and we can confirm that
>>>> there is a deadlock problem that I think needs to be addressed in core code [2].
>>>
>>> Any reason why you didn't cc: us on these patches?
>>
>> We can't apply this "drivers/core: Remove lockdep_set_novalidate_class() usage" patch
> 
> What patch is that?  I do not see that in my inbox anywhere.  I don't
> even see it in my lkml archive, so I do not know what you are talking
> about.

Here is a copy. Please don't apply to git trees, or syzbot will fail to test kernels.

 From f7ff56455ae7813768c6ab85e8e3db374122f32b Mon Sep 17 00:00:00 2001
From: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
Date: Mon, 23 Jan 2023 19:32:26 +0900
Subject: [PATCH] drivers/core: Remove lockdep_set_novalidate_class() usage

This patch experimentally removes lockdep_set_novalidate_class() call
 from device_initialize() introduced by commit 1704f47b50b5 ("lockdep:
Add novalidate class for dev->mutex conversion"), for this commit made it
impossible to find real deadlocks unless timing dependent testings manage
to trigger hung task like [1] and [2]. Let's try if we can find remaining
drivers which need to use separate classes without causing too many crashes
to continue.

[1] https://syzkaller.appspot.com/bug?extid=2d6ac90723742279e101
[2] https://syzkaller.appspot.com/bug?extid=2e39bc6569d281acbcfb

Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
---
 drivers/base/core.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/drivers/base/core.c b/drivers/base/core.c
index a3e14143ec0c..68189722e343 100644
--- a/drivers/base/core.c
+++ b/drivers/base/core.c
@@ -2941,7 +2941,6 @@ void device_initialize(struct device *dev)
 	kobject_init(&dev->kobj, &device_ktype);
 	INIT_LIST_HEAD(&dev->dma_pools);
 	mutex_init(&dev->mutex);
-	lockdep_set_novalidate_class(&dev->mutex);
 	spin_lock_init(&dev->devres_lock);
 	INIT_LIST_HEAD(&dev->devres_head);
 	device_pm_init(dev);
-- 
2.18.4


> 
>> until we fix all lockdep warnings that happen during the boot stage;
> 
> What lockdep warnings?

Here is an example that you will be able to observe by applying the patch above.

----------
[    2.276394][    T9] Trying to unpack rootfs image as initramfs...
[    2.276394][    T1] software IO TLB: mapped [mem 0x00000000bbed0000-0x00000000bfed0000] (64MB)
[    2.276394][    T1] workingset: timestamp_bits=46 max_order=21 bucket_order=0
[    2.276394][    T1] SGI XFS with ACLs, security attributes, verbose warnings, quota, no debug enabled
[    2.276394][    T1] Block layer SCSI generic (bsg) driver version 0.4 loaded (major 252)
[    2.837244][    T1] 
[    2.837244][    T1] ============================================
[    2.837244][    T1] WARNING: possible recursive locking detected
[    2.837244][    T1] 6.2.0-rc5+ #10 Not tainted
[    2.837244][    T1] --------------------------------------------
[    2.837244][    T1] swapper/0/1 is trying to acquire lock:
[    2.837244][    T1] ffff984dc3d50108 (&dev->mutex){+.+.}-{3:3}, at: __device_attach+0x35/0x1a0
[    2.837244][    T1] 
[    2.837244][    T1] but task is already holding lock:
[    2.837244][    T1] ffff984dc1b5e1b8 (&dev->mutex){+.+.}-{3:3}, at: __device_driver_lock+0x28/0x40
[    2.837244][    T1] 
[    2.837244][    T1] other info that might help us debug this:
[    2.837244][    T1]  Possible unsafe locking scenario:
[    2.837244][    T1] 
[    2.837244][    T1]        CPU0
[    2.837244][    T1]        ----
[    2.837244][    T1]   lock(&dev->mutex);
[    2.837244][    T1]   lock(&dev->mutex);
[    2.837244][    T1] 
[    2.837244][    T1]  *** DEADLOCK ***
[    2.837244][    T1] 
[    2.837244][    T1]  May be due to missing lock nesting notation
[    2.837244][    T1] 
[    2.837244][    T1] 1 lock held by swapper/0/1:
[    2.837244][    T1]  #0: ffff984dc1b5e1b8 (&dev->mutex){+.+.}-{3:3}, at: __device_driver_lock+0x28/0x40
[    2.837244][    T1] 
[    2.837244][    T1] stack backtrace:
[    2.837244][    T1] CPU: 7 PID: 1 Comm: swapper/0 Not tainted 6.2.0-rc5+ #10
[    2.837244][    T1] Hardware name: VMware, Inc. VMware Virtual Platform/440BX Desktop Reference Platform, BIOS 6.00 11/12/2020
[    2.837244][    T1] Call Trace:
[    2.837244][    T1]  <TASK>
[    2.837244][    T1]  dump_stack_lvl+0x49/0x5e
[    2.837244][    T1]  dump_stack+0x10/0x12
[    2.837244][    T1]  __lock_acquire.cold.73+0x12e/0x2c7
[    2.837244][    T1]  lock_acquire+0xc7/0x2e0
[    2.837244][    T1]  ? __device_attach+0x35/0x1a0
[    2.837244][    T1]  __mutex_lock+0x99/0xf00
[    2.837244][    T1]  ? __device_attach+0x35/0x1a0
[    2.837244][    T1]  ? __this_cpu_preempt_check+0x13/0x20
[    2.837244][    T1]  ? __device_attach+0x35/0x1a0
[    2.837244][    T1]  ? kobject_uevent_env+0x12f/0x770
[    2.837244][    T1]  mutex_lock_nested+0x16/0x20
[    2.837244][    T1]  ? mutex_lock_nested+0x16/0x20
[    2.837244][    T1]  __device_attach+0x35/0x1a0
[    2.837244][    T1]  device_initial_probe+0xe/0x10
[    2.837244][    T1]  bus_probe_device+0x9b/0xb0
[    2.837244][    T1]  device_add+0x3e1/0x900
[    2.837244][    T1]  ? __init_waitqueue_head+0x4a/0x70
[    2.837244][    T1]  device_register+0x15/0x20
[    2.837244][    T1]  pcie_portdrv_probe+0x3e3/0x670
[    2.837244][    T1]  ? trace_hardirqs_on+0x3b/0x100
[    2.837244][    T1]  pci_device_probe+0xa8/0x150
[    2.837244][    T1]  really_probe+0xd9/0x340
[    2.837244][    T1]  ? pm_runtime_barrier+0x52/0xb0
[    2.837244][    T1]  __driver_probe_device+0x78/0x170
[    2.837244][    T1]  driver_probe_device+0x1f/0x90
[    2.837244][    T1]  __driver_attach+0xaa/0x160
[    2.837244][    T1]  ? __device_attach_driver+0x100/0x100
[    2.837244][    T1]  bus_for_each_dev+0x75/0xb0
[    2.837244][    T1]  driver_attach+0x19/0x20
[    2.837244][    T1]  bus_add_driver+0x1be/0x210
[    2.837244][    T1]  ? dmi_pcie_pme_disable_msi+0x1f/0x1f
[    2.837244][    T1]  ? dmi_pcie_pme_disable_msi+0x1f/0x1f
[    2.837244][    T1]  ? rdinit_setup+0x27/0x27
[    2.837244][    T1]  driver_register+0x6b/0xc0
[    2.837244][    T1]  ? dmi_pcie_pme_disable_msi+0x1f/0x1f
[    2.837244][    T1]  __pci_register_driver+0x7c/0x80
[    2.837244][    T1]  pcie_portdrv_init+0x3d/0x45
[    2.837244][    T1]  do_one_initcall+0x58/0x300
[    2.837244][    T1]  ? rdinit_setup+0x27/0x27
[    2.837244][    T1]  ? rcu_read_lock_sched_held+0x4a/0x70
[    2.837244][    T1]  kernel_init_freeable+0x181/0x1d2
[    2.837244][    T1]  ? rest_init+0x190/0x190
[    2.837244][    T1]  kernel_init+0x15/0x120
[    2.837244][    T1]  ret_from_fork+0x1f/0x30
[    2.837244][    T1]  </TASK>
[    4.126397][    T1] pcieport 0000:00:15.0: PME: Signaling with IRQ 24
[    4.126397][    T1] pcieport 0000:00:15.0: pciehp: Slot #160 AttnBtn+ PwrCtrl+ MRL- AttnInd- PwrInd- HotPlug+ Surprise- Interlock- NoCompl+ IbPresDis- LLActRep+
[    4.126397][    T1] pcieport 0000:00:15.1: PME: Signaling with IRQ 25
----------

# ./scripts/faddr2line --list vmlinux __device_attach+0x35/0x1a0 __device_driver_lock+0x28/0x40
__device_attach+0x35/0x1a0:

__device_attach at drivers/base/dd.c:984
 979    {
 980            int ret = 0;
 981            bool async = false;
 982
 983            device_lock(dev);
>984<           if (dev->p->dead) {
 985                    goto out_unlock;
 986            } else if (dev->driver) {
 987                    if (device_is_bound(dev)) {
 988                            ret = 1;
 989                            goto out_unlock;

__device_driver_lock+0x28/0x40:

__device_driver_lock at drivers/base/dd.c:1074
 1069   static void __device_driver_lock(struct device *dev, struct device *parent)
 1070   {
 1071           if (parent && dev->bus->need_parent_lock)
 1072                   device_lock(parent);
 1073           device_lock(dev);
>1074<  }
 1075
 1076   /*
 1077    * __device_driver_unlock - release locks needed to manipulate dev->drv
 1078    * @dev: Device we will update driver info for
 1079    * @parent: Parent device. Needed if the bus requires parent lock

# ./scripts/faddr2line vmlinux __device_attach+0x35/0x1a0 device_initial_probe+0xe/0x10 bus_probe_device+0x9b/0xb0 device_add+0x3e1/0x900 device_register+0x15/0x20 pcie_portdrv_probe+0x3e3/0x670 pci_device_probe+0xa8/0x150 really_probe+0xd9/0x340 __driver_probe_device+0x78/0x170 driver_probe_device+0x1f/0x90 __driver_attach+0xaa/0x160 bus_for_each_dev+0x75/0xb0 driver_attach+0x19/0x20 bus_add_driver+0x1be/0x210 driver_register+0x6b/0xc0
__device_attach+0x35/0x1a0:
__device_attach at drivers/base/dd.c:984

device_initial_probe+0xe/0x10:
device_initial_probe at drivers/base/dd.c:1058

bus_probe_device+0x9b/0xb0:
bus_probe_device at drivers/base/bus.c:487

device_add+0x3e1/0x900:
device_add at drivers/base/core.c:3485

device_register+0x15/0x20:
device_register at drivers/base/core.c:3560

pcie_portdrv_probe+0x3e3/0x670:
pcie_device_init at drivers/pci/pcie/portdrv.c:310
(inlined by) pcie_port_device_register at drivers/pci/pcie/portdrv.c:363
(inlined by) pcie_portdrv_probe at drivers/pci/pcie/portdrv.c:696

pci_device_probe+0xa8/0x150:
local_pci_probe at drivers/pci/pci-driver.c:324
(inlined by) pci_call_probe at drivers/pci/pci-driver.c:392
(inlined by) __pci_device_probe at drivers/pci/pci-driver.c:417
(inlined by) pci_device_probe at drivers/pci/pci-driver.c:460

really_probe+0xd9/0x340:
call_driver_probe at drivers/base/dd.c:560
(inlined by) really_probe at drivers/base/dd.c:639

__driver_probe_device+0x78/0x170:
__driver_probe_device at drivers/base/dd.c:778

driver_probe_device+0x1f/0x90:
driver_probe_device at drivers/base/dd.c:808

__driver_attach+0xaa/0x160:
__driver_attach at drivers/base/dd.c:1195

bus_for_each_dev+0x75/0xb0:
bus_for_each_dev at drivers/base/bus.c:300

driver_attach+0x19/0x20:
driver_attach at drivers/base/dd.c:1212

bus_add_driver+0x1be/0x210:
bus_add_driver at drivers/base/bus.c:619

driver_register+0x6b/0xc0:
driver_register at drivers/base/driver.c:246

> 
>> otherwise syzbot testing can't work which is more painful than
>> applying this patch now.
> 
> Again, I'm totally confused.  What is the real bug/problem/issue here?

Since the possibility of deadlock is not reported by lockdep, we can't find
real deadlocks unless khungtaskd reports it as a hung task.

> 
> Where is the deadlock?

In driver core code (an example shown above) and in many driver codes
(an example shown below). Since dev->mutex is hidden from lockdep checks,
real deadlocks cannot be reported until khungtaskd reports as hung tasks.

----------
INFO: task syz-executor145:4505 blocked for more than 143 seconds.
Not tainted 6.1.0-rc5-syzkaller-00008-ge01d50cbd6ee #0
"echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
task:syz-executor145 state:D stack:21896 pid:4505 ppid:3645 flags:0x00004002
Call Trace:
<TASK>
context_switch kernel/sched/core.c:5191 [inline]
__schedule+0x8c9/0xd70 kernel/sched/core.c:6503
schedule+0xcb/0x190 kernel/sched/core.c:6579
schedule_preempt_disabled+0xf/0x20 kernel/sched/core.c:6638
__mutex_lock_common+0xe4f/0x26e0 kernel/locking/mutex.c:679
__mutex_lock kernel/locking/mutex.c:747 [inline]
mutex_lock_nested+0x17/0x20 kernel/locking/mutex.c:799
rfkill_unregister+0xcb/0x220 net/rfkill/core.c:1130
nfc_unregister_device+0xba/0x290 net/nfc/core.c:1167
virtual_ncidev_close+0x55/0x90 drivers/nfc/virtual_ncidev.c:166
__fput+0x3ba/0x880 fs/file_table.c:320
task_work_run+0x243/0x300 kernel/task_work.c:179
exit_task_work include/linux/task_work.h:38 [inline]
do_exit+0x664/0x2070 kernel/exit.c:820
do_group_exit+0x1fd/0x2b0 kernel/exit.c:950
__do_sys_exit_group kernel/exit.c:961 [inline]
__se_sys_exit_group kernel/exit.c:959 [inline]
__x64_sys_exit_group+0x3b/0x40 kernel/exit.c:959
do_syscall_x64 arch/x86/entry/common.c:50 [inline]
do_syscall_64+0x3d/0xb0 arch/x86/entry/common.c:80
entry_SYSCALL_64_after_hwframe+0x63/0xcd
RIP: 0033:0x7fc8e3d92af9
RSP: 002b:00007fff2cfab0b8 EFLAGS: 00000246 ORIG_RAX: 00000000000000e7
RAX: ffffffffffffffda RBX: 00007fc8e3e06330 RCX: 00007fc8e3d92af9
RDX: 000000000000003c RSI: 00000000000000e7 RDI: 0000000000000000
RBP: 0000000000000000 R08: ffffffffffffffc0 R09: 0000000000000001
R10: 0000000000000001 R11: 0000000000000246 R12: 00007fc8e3e06330
R13: 0000000000000001 R14: 0000000000000000 R15: 0000000000000001
</TASK> 
INFO: task syz-executor145:4516 blocked for more than 144 seconds.
Not tainted 6.1.0-rc5-syzkaller-00008-ge01d50cbd6ee #0
"echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
task:syz-executor145 state:D stack:23096 pid:4516 ppid:3647 flags:0x00004004
Call Trace:
<TASK>
context_switch kernel/sched/core.c:5191 [inline]
__schedule+0x8c9/0xd70 kernel/sched/core.c:6503
schedule+0xcb/0x190 kernel/sched/core.c:6579
schedule_preempt_disabled+0xf/0x20 kernel/sched/core.c:6638
__mutex_lock_common+0xe4f/0x26e0 kernel/locking/mutex.c:679
__mutex_lock kernel/locking/mutex.c:747 [inline]
mutex_lock_nested+0x17/0x20 kernel/locking/mutex.c:799
device_lock include/linux/device.h:835 [inline]
nfc_dev_down+0x33/0x260 net/nfc/core.c:143
nfc_rfkill_set_block+0x28/0xc0 net/nfc/core.c:179
rfkill_set_block+0x1e7/0x430 net/rfkill/core.c:345
rfkill_fop_write+0x5db/0x790 net/rfkill/core.c:1286
vfs_write+0x303/0xc50 fs/read_write.c:582
ksys_write+0x177/0x2a0 fs/read_write.c:637
do_syscall_x64 arch/x86/entry/common.c:50 [inline]
do_syscall_64+0x3d/0xb0 arch/x86/entry/common.c:80
entry_SYSCALL_64_after_hwframe+0x63/0xcd
RIP: 0033:0x7fc8e3d93e69
RSP: 002b:00007fff2cfab108 EFLAGS: 00000246 ORIG_RAX: 0000000000000001
RAX: ffffffffffffffda RBX: 00000000000f4240 RCX: 00007fc8e3d93e69
RDX: 0000000000000008 RSI: 0000000020000000 RDI: 0000000000000003
RBP: 0000000000000000 R08: 0000000000000001 R09: 0000000000000001
R10: 0000000000000001 R11: 0000000000000246 R12: 000000000000d60b
R13: 00007fff2cfab11c R14: 00007fff2cfab130 R15: 00007fff2cfab120
</TASK> 
----------

----------
2 locks held by syz-executor145/4505:
#0: ffff88807268e100 (&dev->mutex){....}-{3:3}, at: device_lock include/linux/device.h:835 [inline]
#0: ffff88807268e100 (&dev->mutex){....}-{3:3}, at: nfc_unregister_device+0x87/0x290 net/nfc/core.c:1165
#1: ffffffff8e787b08 (rfkill_global_mutex){+.+.}-{3:3}, at: rfkill_unregister+0xcb/0x220 net/rfkill/core.c:1130
2 locks held by syz-executor145/4516:
#0: ffffffff8e787b08 (rfkill_global_mutex){+.+.}-{3:3}, at: rfkill_fop_write+0x1b3/0x790 net/rfkill/core.c:1278
#1: ffff88807268e100 (&dev->mutex){....}-{3:3}, at: device_lock include/linux/device.h:835 [inline]
#1: ffff88807268e100 (&dev->mutex){....}-{3:3}, at: nfc_dev_down+0x33/0x260 net/nfc/core.c:143
----------

> 
>> Therefore, I locally tested this patch (in order not to be applied now).
> 
> What patch?  I'm totally confused.

The "drivers/core: Remove lockdep_set_novalidate_class() usage" shown above.

> 
>> And I got a lockdep warning on the perf_event code.
> 
> What warning?

Here is a copy.

----------
[    2.241650][    T9] Trying to unpack rootfs image as initramfs...
[    2.241630][    T1] software IO TLB: mapped [mem 0x00000000bbed0000-0x00000000bfed0000] (64MB)
[    2.241670][    T1] workingset: timestamp_bits=46 max_order=21 bucket_order=0
[    2.241670][    T1] SGI XFS with ACLs, security attributes, verbose warnings, quota, no debug enabled
[    2.241670][    T1] Block layer SCSI generic (bsg) driver version 0.4 loaded (major 252)
[    2.798150][    T1] 
[    2.798660][    T1] ======================================================
[    2.798660][    T1] WARNING: possible circular locking dependency detected
[    2.798660][    T1] 6.2.0-rc5+ #9 Not tainted
[    2.798660][    T1] ------------------------------------------------------
[    2.798660][    T1] swapper/0/1 is trying to acquire lock:
[    2.798660][    T1] ffffffffb002e888 (cpu_add_remove_lock){+.+.}-{3:3}, at: cpu_hotplug_disable+0x12/0x30
[    2.798660][    T1] 
[    2.798660][    T1] but task is already holding lock:
[    2.798660][    T1] ffff941940a161b8 (&dev->mutex){+.+.}-{3:3}, at: __device_driver_lock+0x28/0x40
[    2.798660][    T1] 
[    2.798660][    T1] which lock already depends on the new lock.
[    2.798660][    T1] 
[    2.798660][    T1] 
[    2.798660][    T1] the existing dependency chain (in reverse order) is:
[    2.798660][    T1] 
[    2.798660][    T1] -> #3 (&dev->mutex){+.+.}-{3:3}:
[    2.798660][    T1]        lock_acquire+0xc7/0x2e0
[    2.798660][    T1]        __mutex_lock+0x99/0xf00
[    2.798660][    T1]        mutex_lock_nested+0x16/0x20
[    2.798660][    T1]        __device_attach+0x35/0x1a0
[    2.798660][    T1]        device_initial_probe+0xe/0x10
[    2.798660][    T1]        bus_probe_device+0x9b/0xb0
[    2.798660][    T1]        device_add+0x3e1/0x900
[    2.798660][    T1]        pmu_dev_alloc+0x98/0xf0
[    2.798660][    T1]        perf_event_sysfs_init+0x56/0x8f
[    2.798660][    T1]        do_one_initcall+0x58/0x300
[    2.798660][    T1]        kernel_init_freeable+0x181/0x1d2
[    2.798660][    T1]        kernel_init+0x15/0x120
[    2.798660][    T1]        ret_from_fork+0x1f/0x30
[    2.798660][    T1] 
[    2.798660][    T1] -> #2 (pmus_lock){+.+.}-{3:3}:
[    2.798660][    T1]        lock_acquire+0xc7/0x2e0
[    2.798660][    T1]        __mutex_lock+0x99/0xf00
[    2.798660][    T1]        mutex_lock_nested+0x16/0x20
[    2.798660][    T1]        perf_event_init_cpu+0x4c/0x110
[    2.798660][    T1]        cpuhp_invoke_callback+0x17a/0x880
[    2.798660][    T1]        __cpuhp_invoke_callback_range+0x77/0xb0
[    2.798660][    T1]        _cpu_up+0xdc/0x240
[    2.798660][    T1]        cpu_up+0x8c/0xa0
[    2.798660][    T1]        bringup_nonboot_cpus+0x56/0x60
[    2.798660][    T1]        smp_init+0x25/0x5f
[    2.798660][    T1]        kernel_init_freeable+0xb4/0x1d2
[    2.798660][    T1]        kernel_init+0x15/0x120
[    2.798660][    T1]        ret_from_fork+0x1f/0x30
[    2.798660][    T1] 
[    2.798660][    T1] -> #1 (cpu_hotplug_lock){++++}-{0:0}:
[    2.798660][    T1]        lock_acquire+0xc7/0x2e0
[    2.798660][    T1]        percpu_down_write+0x44/0x2c0
[    2.798660][    T1]        _cpu_up+0x35/0x240
[    2.798660][    T1]        cpu_up+0x8c/0xa0
[    2.798660][    T1]        bringup_nonboot_cpus+0x56/0x60
[    2.798660][    T1]        smp_init+0x25/0x5f
[    2.798660][    T1]        kernel_init_freeable+0xb4/0x1d2
[    2.798660][    T1]        kernel_init+0x15/0x120
[    2.798660][    T1]        ret_from_fork+0x1f/0x30
[    2.798660][    T1] 
[    2.798660][    T1] -> #0 (cpu_add_remove_lock){+.+.}-{3:3}:
[    2.798660][    T1]        check_prevs_add+0x16a/0x1070
[    2.798660][    T1]        __lock_acquire+0x11bd/0x1670
[    2.798660][    T1]        lock_acquire+0xc7/0x2e0
[    2.798660][    T1]        __mutex_lock+0x99/0xf00
[    2.798660][    T1]        mutex_lock_nested+0x16/0x20
[    2.798660][    T1]        cpu_hotplug_disable+0x12/0x30
[    2.798660][    T1]        pci_device_probe+0x8c/0x150
[    2.798660][    T1]        really_probe+0xd9/0x340
[    2.798660][    T1]        __driver_probe_device+0x78/0x170
[    2.798660][    T1]        driver_probe_device+0x1f/0x90
[    2.798660][    T1]        __driver_attach+0xaa/0x160
[    2.798660][    T1]        bus_for_each_dev+0x75/0xb0
[    2.798660][    T1]        driver_attach+0x19/0x20
[    2.798660][    T1]        bus_add_driver+0x1be/0x210
[    2.798660][    T1]        driver_register+0x6b/0xc0
[    2.798660][    T1]        __pci_register_driver+0x7c/0x80
[    2.798660][    T1]        pcie_portdrv_init+0x3d/0x45
[    2.798660][    T1]        do_one_initcall+0x58/0x300
[    2.798660][    T1]        kernel_init_freeable+0x181/0x1d2
[    2.798660][    T1]        kernel_init+0x15/0x120
[    2.798660][    T1]        ret_from_fork+0x1f/0x30
[    2.798660][    T1] 
[    2.798660][    T1] other info that might help us debug this:
[    2.798660][    T1] 
[    2.798660][    T1] Chain exists of:
[    2.798660][    T1]   cpu_add_remove_lock --> pmus_lock --> &dev->mutex
[    2.798660][    T1] 
[    2.798660][    T1]  Possible unsafe locking scenario:
[    2.798660][    T1] 
[    2.798660][    T1]        CPU0                    CPU1
[    2.798660][    T1]        ----                    ----
[    2.798660][    T1]   lock(&dev->mutex);
[    2.798660][    T1]                                lock(pmus_lock);
[    2.798660][    T1]                                lock(&dev->mutex);
[    2.798660][    T1]   lock(cpu_add_remove_lock);
[    2.798660][    T1] 
[    2.798660][    T1]  *** DEADLOCK ***
[    2.798660][    T1] 
[    2.798660][    T1] 1 lock held by swapper/0/1:
[    2.798660][    T1]  #0: ffff941940a161b8 (&dev->mutex){+.+.}-{3:3}, at: __device_driver_lock+0x28/0x40
[    2.798660][    T1] 
[    2.798660][    T1] stack backtrace:
[    2.798660][    T1] CPU: 3 PID: 1 Comm: swapper/0 Not tainted 6.2.0-rc5+ #9
[    2.798660][    T1] Hardware name: VMware, Inc. VMware Virtual Platform/440BX Desktop Reference Platform, BIOS 6.00 11/12/2020
[    2.798660][    T1] Call Trace:
[    2.798660][    T1]  <TASK>
[    2.798660][    T1]  dump_stack_lvl+0x49/0x5e
[    2.798660][    T1]  dump_stack+0x10/0x12
[    2.798660][    T1]  print_circular_bug.isra.46.cold.66+0x13e/0x143
[    2.798660][    T1]  check_noncircular+0xfe/0x110
[    2.798660][    T1]  check_prevs_add+0x16a/0x1070
[    2.798660][    T1]  __lock_acquire+0x11bd/0x1670
[    2.798660][    T1]  lock_acquire+0xc7/0x2e0
[    2.798660][    T1]  ? cpu_hotplug_disable+0x12/0x30
[    2.798660][    T1]  __mutex_lock+0x99/0xf00
[    2.798660][    T1]  ? cpu_hotplug_disable+0x12/0x30
[    2.798660][    T1]  ? pci_match_device+0xd5/0x130
[    2.798660][    T1]  ? __this_cpu_preempt_check+0x13/0x20
[    2.798660][    T1]  ? cpu_hotplug_disable+0x12/0x30
[    2.798660][    T1]  ? kernfs_add_one+0xf1/0x130
[    2.798660][    T1]  mutex_lock_nested+0x16/0x20
[    2.798660][    T1]  ? mutex_lock_nested+0x16/0x20
[    2.798660][    T1]  cpu_hotplug_disable+0x12/0x30
[    2.798660][    T1]  pci_device_probe+0x8c/0x150
[    2.798660][    T1]  really_probe+0xd9/0x340
[    2.798660][    T1]  ? pm_runtime_barrier+0x52/0xb0
[    2.798660][    T1]  __driver_probe_device+0x78/0x170
[    2.798660][    T1]  driver_probe_device+0x1f/0x90
[    2.798660][    T1]  __driver_attach+0xaa/0x160
[    2.798660][    T1]  ? __device_attach_driver+0x100/0x100
[    2.798660][    T1]  bus_for_each_dev+0x75/0xb0
[    2.798660][    T1]  driver_attach+0x19/0x20
[    2.798660][    T1]  bus_add_driver+0x1be/0x210
[    2.798660][    T1]  ? dmi_pcie_pme_disable_msi+0x1f/0x1f
[    2.798660][    T1]  ? dmi_pcie_pme_disable_msi+0x1f/0x1f
[    2.798660][    T1]  ? rdinit_setup+0x27/0x27
[    2.798660][    T1]  driver_register+0x6b/0xc0
[    2.798660][    T1]  ? dmi_pcie_pme_disable_msi+0x1f/0x1f
[    2.798660][    T1]  __pci_register_driver+0x7c/0x80
[    2.798660][    T1]  pcie_portdrv_init+0x3d/0x45
[    2.798660][    T1]  do_one_initcall+0x58/0x300
[    2.798660][    T1]  ? rdinit_setup+0x27/0x27
[    2.798660][    T1]  ? rcu_read_lock_sched_held+0x4a/0x70
[    2.798660][    T1]  kernel_init_freeable+0x181/0x1d2
[    2.798660][    T1]  ? rest_init+0x190/0x190
[    2.798660][    T1]  kernel_init+0x15/0x120
[    2.798660][    T1]  ret_from_fork+0x1f/0x30
[    2.798660][    T1]  </TASK>
[    3.991673][   T92] tsc: Refined TSC clocksource calibration: 2611.210 MHz
[    3.991673][   T92] clocksource: tsc: mask: 0xffffffffffffffff max_cycles: 0x25a399d04c4, max_idle_ns: 440795206293 ns
[    4.992946][   T92] clocksource: Switched to clocksource tsc
----------


> 
>> I got next lockdep warning on the driver core code when I tried a fix
>> for the perf_event code suggested by Peter Zijlstra.
> 
> Again, what warning?

Shown above.

[    2.837244][    T1] swapper/0/1 is trying to acquire lock:
[    2.837244][    T1] ffff984dc3d50108 (&dev->mutex){+.+.}-{3:3}, at: __device_attach+0x35/0x1a0
[    2.837244][    T1] 
[    2.837244][    T1] but task is already holding lock:
[    2.837244][    T1] ffff984dc1b5e1b8 (&dev->mutex){+.+.}-{3:3}, at: __device_driver_lock+0x28/0x40
[    2.837244][    T1] 
[    2.837244][    T1] other info that might help us debug this:
[    2.837244][    T1]  Possible unsafe locking scenario:
[    2.837244][    T1] 
[    2.837244][    T1]        CPU0
[    2.837244][    T1]        ----
[    2.837244][    T1]   lock(&dev->mutex);
[    2.837244][    T1]   lock(&dev->mutex);
[    2.837244][    T1] 
[    2.837244][    T1]  *** DEADLOCK ***

> 
>> Since Peter confirmed that this is a problem that led to commit
>> 1704f47b50b5 ("lockdep: Add novalidate class for dev->mutex
>> conversion"), this time I'm reporting this problem to you (so that you
>> can propose a fix for the driver core code).
> 
> Again, I have no idea what the real problem is!

Since dev->mutex is hidden from lockdep checks, real deadlocks cannot be
reported until khungtaskd reports as hung tasks.

> 
> Please show me in the driver core code, where the deadlock is that needs
> to be resolved.  Without that, I can't answer anything...
> 
> totally and throughly confused,
> 
> greg k-h

Re: Converting dev->mutex into dev->spinlock ?

[Tetsuo Handa]

On 2023/02/05 0:12, Alan Stern wrote:
>>  it would solve many deadlocks in driver code if you can update
> 
> What deadlocks?  If there are so many deadlocks floating around in 
> driver code, why haven't we heard about them before now?

Since dev->mutex is hidden from lockdep checks, nobody can see lockdep warnings.
syzbot is reporting real deadlocks without lockdep warnings, for the fundamental
problem you mentioned in https://lkml.kernel.org/r/Pine.LNX.4.44L0.0804171117450.18040-100000@iolanthe.rowland.org
is remaining. I'm suggesting you that now is time to address this fundamental problem.

>> (by e.g. replacing dev->mutex with dev->spinlock and dev->atomic_flags).
>> But I'm not familiar enough to propose such change...
> 
> Such a change cannot be made.  Consider this: Driver callbacks often
> need to sleep.  But when a thread holds a spinlock, it is not allowed to 
> sleep.  Therefore driver callbacks must not be invoked while a spinlock 
> is held.

What I'm suggesting is "Do not call driver callbacks with dev->mutex held,
by rewriting driver core code".

Re: Converting dev->mutex into dev->spinlock ?

[Alan Stern]

On Sat, Feb 04, 2023 at 11:21:27PM +0900, Tetsuo Handa wrote:
> On 2023/02/04 22:47, Greg Kroah-Hartman wrote:
> > On Sat, Feb 04, 2023 at 10:32:11PM +0900, Tetsuo Handa wrote:
> >> Hello.
> >>
> >> There is a long-standing deadlock problem in driver core code caused by
> >> "struct device"->mutex being marked as "do not apply lockdep checks".
> > 
> > The marking of a lock does not cause a deadlock problem, so what do you
> > mean exactly by this?  Where is the actual deadlock?
> 
> A few of examples:
> 
>   https://syzkaller.appspot.com/bug?extid=2d6ac90723742279e101

It's hard to figure out what's wrong from looking at the syzbot report.  
What makes you think it is connected with dev->mutex?

At first glance, it seems that the ath6kl driver is trying to flush a 
workqueue while holding a lock or mutex that is needed by one of the 
jobs in the workqueue.  That's obviously never going to work, no matter 
what sort of lockdep validation gets used.

>   https://syzkaller.appspot.com/bug?extid=2e39bc6569d281acbcfb
>   https://syzkaller.appspot.com/bug?extid=9ef743bba3a17c756174
> 
> > 
> >> We can make this deadlock visible by applying [1], and we can confirm that
> >> there is a deadlock problem that I think needs to be addressed in core code [2].
> > 
> > Any reason why you didn't cc: us on these patches?
> 
> We can't apply this "drivers/core: Remove lockdep_set_novalidate_class() usage" patch
> until we fix all lockdep warnings that happen during the boot stage; otherwise syzbot
> testing can't work which is more painful than applying this patch now.
> 
> Therefore, I locally tested this patch (in order not to be applied now). And I got
> a lockdep warning on the perf_event code. I got next lockdep warning on the driver core
> code when I tried a fix for the perf_event code suggested by Peter Zijlstra. Since Peter
> confirmed that this is a problem that led to commit 1704f47b50b5 ("lockdep: Add novalidate
> class for dev->mutex conversion"), this time I'm reporting this problem to you (so that
> you can propose a fix for the driver core code).

There is no fix.  This problem is inherent to the way that lockdep 
works.

Lockdep classifies locks into classes, and it reports a problem if there 
is a locking cycle (for example, if someone tries to acquire a lock in 
class B while holding a lock in class A, someone else tries to acquire a 
lock in class C while holding a lock in class B, and someone else tries 
to acquire a lock in class A while holding a lock in class C).

But this sort of approach doesn't work when you're dealing with a 
recursive locking structure such as the device tree.  Here all the 
dev->mutex locks belong to the same class, so lockdep thinks there's a 
problem whenever someone tries to lock a device while holding another 
device's lock.

However, it is always safe to acquire a child device's lock while 
holding the parent's lock.  Lockdep isn't aware of this because it 
doesn't understand the hierarchical device tree.  That's why lockdep 
checking has to be disabled for dev->mutex; if it weren't disabled then 
it would constantly report false positives.

Alan Stern

Re: Converting dev->mutex into dev->spinlock ?

[Alan Stern]

On Sun, Feb 05, 2023 at 12:30:07AM +0900, Tetsuo Handa wrote:
> On 2023/02/05 0:12, Alan Stern wrote:
> >>  it would solve many deadlocks in driver code if you can update
> > 
> > What deadlocks?  If there are so many deadlocks floating around in 
> > driver code, why haven't we heard about them before now?
> 
> Since dev->mutex is hidden from lockdep checks, nobody can see lockdep warnings.
> syzbot is reporting real deadlocks without lockdep warnings, for the fundamental
> problem you mentioned in https://lkml.kernel.org/r/Pine.LNX.4.44L0.0804171117450.18040-100000@iolanthe.rowland.org
> is remaining. I'm suggesting you that now is time to address this fundamental problem.

Maybe so.  But the place to address it is inside lockdep, not in the 
driver core.

> >> (by e.g. replacing dev->mutex with dev->spinlock and dev->atomic_flags).
> >> But I'm not familiar enough to propose such change...
> > 
> > Such a change cannot be made.  Consider this: Driver callbacks often
> > need to sleep.  But when a thread holds a spinlock, it is not allowed to 
> > sleep.  Therefore driver callbacks must not be invoked while a spinlock 
> > is held.
> 
> What I'm suggesting is "Do not call driver callbacks with dev->mutex held,
> by rewriting driver core code".

That cannot be done.  The only possible solution is to teach lockdep how 
to handle recursive locking structures.

Alan Stern

Re: Converting dev->mutex into dev->spinlock ?

[Tetsuo Handa]

On 2023/02/05 0:34, Alan Stern wrote:
>> A few of examples:
>>
>>   https://syzkaller.appspot.com/bug?extid=2d6ac90723742279e101
> 
> It's hard to figure out what's wrong from looking at the syzbot report.  
> What makes you think it is connected with dev->mutex?
> 
> At first glance, it seems that the ath6kl driver is trying to flush a 
> workqueue while holding a lock or mutex that is needed by one of the 
> jobs in the workqueue.  That's obviously never going to work, no matter 
> what sort of lockdep validation gets used.

That lock is exactly dev->mutex where lockdep validation is disabled.
If lockdep validation on dev->mutex were not disabled, we can catch
possibility of deadlock before khungtaskd reports real deadlock as hung.

Lockdep validation on dev->mutex being disabled is really annoying, and
I want to make lockdep validation on dev->mutex enabled; that is the
"drivers/core: Remove lockdep_set_novalidate_class() usage" patch.

-------- Forwarded Message --------
Message-ID: <5e4d20a0-08a3-9736-b6ef-cda00acca63f@I-love.SAKURA.ne.jp>
Date: Sun, 3 Jul 2022 23:29:16 +0900
From: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
Subject: Re: INFO: task hung in ath6kl_usb_power_off

I finally found why lockdep was not able to report this deadlock.
device_initialize() was hiding dev->mutex from lockdep tests.
I hope we can get rid of this lockdep_set_novalidate_class()...

Below is a reproducer kernel module. If request_firmware_nowait() called

  INIT_WORK(&fw_work->work, request_firmware_work_func);
  schedule_work(&fw_work->work);

before hub_event() calls

  usb_lock_device(hdev);

, flush_scheduled_work() from hub_event() becomes responsible for flushing
fw_work->work. But flush_scheduled_work() can't flush fw_work->work because
dev->mutex is held by hub_event().

----------------------------------------
#include <linux/module.h>
#include <linux/sched.h>

static DEFINE_MUTEX(mutex);

static void request_firmware_work_func(struct work_struct *work)
{
	schedule_timeout_uninterruptible(HZ); // inject race window for allowing hub_event() to find this work
	mutex_lock(&mutex); // device_lock(parent) from ath9k_hif_usb_firmware_fail() waits for ath6kl_hif_power_off() to release dev->mutex
	mutex_unlock(&mutex); // device_unlock(parent) from ath9k_hif_usb_firmware_fail()
}
static void hub_event(struct work_struct *work)
{
	mutex_lock(&mutex); // usb_lock_device(hdev)
	flush_scheduled_work(); // ath6kl_usb_flush_all() from ath6kl_hif_power_off() waits for request_firmware_work_func() while holding dev->mutex
	mutex_unlock(&mutex); // usb_unlock_device(hdev)
}

static DECLARE_WORK(fw_work, request_firmware_work_func);
static DECLARE_WORK(hub_events, hub_event);

static int __init test_init(void)
{
	lockdep_set_novalidate_class(&mutex); // device_initialize() suppresses lockdep warning
	schedule_work(&fw_work); // request_firmware_nowait() from ath9k driver queues into system_wq
	queue_work(system_freezable_wq, &hub_events); // kick_hub_wq() from usb code queues into hub_wq
	return 0;
}

static void test_exit(void)
{
}

module_init(test_init);
module_exit(test_exit);
MODULE_LICENSE("GPL");
----------------------------------------

----------------------------------------
[   38.832553][ T2786] test: loading out-of-tree module taints kernel.
[  187.116969][   T35] INFO: task kworker/0:2:33 blocked for more than 143 seconds.
[  187.121366][   T35]       Tainted: G           O      5.19.0-rc4-next-20220701 #43
[  187.124830][   T35] "echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
[  187.128724][   T35] task:kworker/0:2     state:D stack:    0 pid:   33 ppid:     2 flags:0x00004000
[  187.133235][   T35] Workqueue: events_freezable hub_event [test]
[  187.136000][   T35] Call Trace:
[  187.137512][   T35]  <TASK>
[  187.138863][   T35]  __schedule+0x304/0x8f0
[  187.140923][   T35]  schedule+0x40/0xa0
[  187.142940][   T35]  schedule_timeout+0x300/0x3a0
[  187.145341][   T35]  ? mark_held_locks+0x55/0x80
[  187.147518][   T35]  ? wait_for_completion+0x6b/0x130
[  187.149257][   T35]  ? _raw_spin_unlock_irq+0x22/0x30
[  187.151187][   T35]  ? wait_for_completion+0x6b/0x130
[  187.152915][   T35]  ? trace_hardirqs_on+0x3b/0xd0
[  187.154388][   T35]  wait_for_completion+0x73/0x130
[  187.155547][   T35]  __flush_workqueue+0x17b/0x480
[  187.156710][   T35]  ? __mutex_lock+0x12b/0xe10
[  187.157703][   T35]  ? wait_for_completion+0x2d/0x130
[  187.158837][   T35]  hub_event+0x1e/0x30 [test]
[  187.160286][   T35]  ? hub_event+0x1e/0x30 [test]
[  187.161352][   T35]  process_one_work+0x292/0x570
[  187.162565][   T35]  worker_thread+0x2f/0x3d0
[  187.163590][   T35]  ? process_one_work+0x570/0x570
[  187.164779][   T35]  kthread+0xd6/0x100
[  187.165940][   T35]  ? kthread_complete_and_exit+0x20/0x20
[  187.167077][   T35]  ret_from_fork+0x1f/0x30
[  187.168319][   T35]  </TASK>
[  187.169190][   T35] INFO: task kworker/0:3:54 blocked for more than 143 seconds.
[  187.171458][   T35]       Tainted: G           O      5.19.0-rc4-next-20220701 #43
[  187.173380][   T35] "echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
[  187.175359][   T35] task:kworker/0:3     state:D stack:    0 pid:   54 ppid:     2 flags:0x00004000
[  187.177660][   T35] Workqueue: events request_firmware_work_func [test]
[  187.179221][   T35] Call Trace:
[  187.180381][   T35]  <TASK>
[  187.181170][   T35]  __schedule+0x304/0x8f0
[  187.182618][   T35]  schedule+0x40/0xa0
[  187.184207][   T35]  schedule_preempt_disabled+0x10/0x20
[  187.186318][   T35]  __mutex_lock+0x650/0xe10
[  187.188527][   T35]  ? request_firmware_work_func+0x1c/0x30 [test]
[  187.190094][   T35]  mutex_lock_nested+0x16/0x20
[  187.191905][   T35]  ? mutex_lock_nested+0x16/0x20
[  187.193159][   T35]  request_firmware_work_func+0x1c/0x30 [test]
[  187.194643][   T35]  process_one_work+0x292/0x570
[  187.195899][   T35]  worker_thread+0x2f/0x3d0
[  187.197031][   T35]  ? process_one_work+0x570/0x570
[  187.198489][   T35]  kthread+0xd6/0x100
[  187.199756][   T35]  ? kthread_complete_and_exit+0x20/0x20
[  187.201224][   T35]  ret_from_fork+0x1f/0x30
[  187.202374][   T35]  </TASK>
[  187.203293][   T35] 
[  187.203293][   T35] Showing all locks held in the system:
[  187.205200][   T35] 1 lock held by rcu_tasks_trace/10:
[  187.206489][   T35]  #0: ffffffffb25bdea0 (rcu_tasks_trace.tasks_gp_mutex){+.+.}-{3:3}, at: rcu_tasks_one_gp+0x28/0x3b0
[  187.209383][   T35] 3 locks held by kworker/0:2/33:
[  187.210930][   T35]  #0: ffff9e2bc004d148 ((wq_completion)events_freezable){+.+.}-{0:0}, at: process_one_work+0x215/0x570
[  187.214012][   T35]  #1: ffffac448032fe68 (hub_events){+.+.}-{0:0}, at: process_one_work+0x215/0x570
[  187.217162][   T35]  #2: ffffffffc067b130 (&dev->mutex){....}-{3:3}, at: hub_event+0x12/0x30 [test]
[  187.220277][   T35] 1 lock held by khungtaskd/35:
[  187.221592][   T35]  #0: ffffffffb25be5c0 (rcu_read_lock){....}-{1:2}, at: rcu_lock_acquire.constprop.56+0x0/0x30
[  187.224310][   T35] 3 locks held by kworker/0:3/54:
[  187.225596][   T35]  #0: ffff9e2bc004cb48 ((wq_completion)events){+.+.}-{0:0}, at: process_one_work+0x215/0x570
[  187.228147][   T35]  #1: ffffac4480cebe68 (fw_work){+.+.}-{0:0}, at: process_one_work+0x215/0x570
[  187.230646][   T35]  #2: ffffffffc067b130 (&dev->mutex){....}-{3:3}, at: request_firmware_work_func+0x1c/0x30 [test]
[  187.234203][   T35] 2 locks held by agetty/2729:
[  187.235463][   T35]  #0: ffff9e2bc71740a0 (&tty->ldisc_sem){++++}-{0:0}, at: ldsem_down_read+0xe/0x10
[  187.237864][   T35]  #1: ffffac448229f2f8 (&ldata->atomic_read_lock){+.+.}-{3:3}, at: n_tty_read+0x168/0x5f0
[  187.240571][   T35] 2 locks held by agetty/2731:
[  187.241876][   T35]  #0: ffff9e2bc907b8a0 (&tty->ldisc_sem){++++}-{0:0}, at: ldsem_down_read+0xe/0x10
[  187.244312][   T35]  #1: ffffac44822a72f8 (&ldata->atomic_read_lock){+.+.}-{3:3}, at: n_tty_read+0x168/0x5f0
[  187.246938][   T35] 
[  187.247756][   T35] =============================================
[  187.247756][   T35] 
----------------------------------------

> However, it is always safe to acquire a child device's lock while 
> holding the parent's lock.  Lockdep isn't aware of this because it 
> doesn't understand the hierarchical device tree.  That's why lockdep 
> checking has to be disabled for dev->mutex; if it weren't disabled then 
> it would constantly report false positives.

Even if it is always safe to acquire a child device's lock while holding
the parent's lock, disabling lockdep checks completely on device's lock is
not safe.

Re: Converting dev->mutex into dev->spinlock ?

[Alan Stern]

On Sun, Feb 05, 2023 at 01:12:12AM +0900, Tetsuo Handa wrote:
> On 2023/02/05 0:34, Alan Stern wrote:
> >> A few of examples:
> >>
> >>   https://syzkaller.appspot.com/bug?extid=2d6ac90723742279e101
> > 
> > It's hard to figure out what's wrong from looking at the syzbot report.  
> > What makes you think it is connected with dev->mutex?
> > 
> > At first glance, it seems that the ath6kl driver is trying to flush a 
> > workqueue while holding a lock or mutex that is needed by one of the 
> > jobs in the workqueue.  That's obviously never going to work, no matter 
> > what sort of lockdep validation gets used.
> 
> That lock is exactly dev->mutex where lockdep validation is disabled.
> If lockdep validation on dev->mutex were not disabled, we can catch
> possibility of deadlock before khungtaskd reports real deadlock as hung.
> 
> Lockdep validation on dev->mutex being disabled is really annoying, and
> I want to make lockdep validation on dev->mutex enabled; that is the
> "drivers/core: Remove lockdep_set_novalidate_class() usage" patch.

> Even if it is always safe to acquire a child device's lock while holding
> the parent's lock, disabling lockdep checks completely on device's lock is
> not safe.

I understand the problem you want to solve, and I understand that it
can be frustrating.  However, I do not believe you will be able to
solve this problem.

Alan Stern

Re: Converting dev->mutex into dev->spinlock ?

[Tetsuo Handa]

On 2023/02/05 1:27, Alan Stern wrote:
> On Sun, Feb 05, 2023 at 01:12:12AM +0900, Tetsuo Handa wrote:
>> On 2023/02/05 0:34, Alan Stern wrote:
>>>> A few of examples:
>>>>
>>>>   https://syzkaller.appspot.com/bug?extid=2d6ac90723742279e101
>>>
>>> It's hard to figure out what's wrong from looking at the syzbot report.  
>>> What makes you think it is connected with dev->mutex?
>>>
>>> At first glance, it seems that the ath6kl driver is trying to flush a 
>>> workqueue while holding a lock or mutex that is needed by one of the 
>>> jobs in the workqueue.  That's obviously never going to work, no matter 
>>> what sort of lockdep validation gets used.
>>
>> That lock is exactly dev->mutex where lockdep validation is disabled.
>> If lockdep validation on dev->mutex were not disabled, we can catch
>> possibility of deadlock before khungtaskd reports real deadlock as hung.
>>
>> Lockdep validation on dev->mutex being disabled is really annoying, and
>> I want to make lockdep validation on dev->mutex enabled; that is the
>> "drivers/core: Remove lockdep_set_novalidate_class() usage" patch.
> 
>> Even if it is always safe to acquire a child device's lock while holding
>> the parent's lock, disabling lockdep checks completely on device's lock is
>> not safe.
> 
> I understand the problem you want to solve, and I understand that it
> can be frustrating.  However, I do not believe you will be able to
> solve this problem.

That is a declaration that driver developers are allowed to take it for granted
that driver callback functions can behave as if dev->mutex is not held. 

Some developers test their changes with lockdep enabled, and believe that their
changes are correct because lockdep did not complain.
https://syzkaller.appspot.com/bug?extid=9ef743bba3a17c756174 is an example.

We should somehow update driver core code to make it possible to keep lockdep
checks enabled on dev->mutex.

Re: Converting dev->mutex into dev->spinlock ?

[Alan Stern]

On Sun, Feb 05, 2023 at 02:09:40AM +0900, Tetsuo Handa wrote:
> On 2023/02/05 1:27, Alan Stern wrote:
> > On Sun, Feb 05, 2023 at 01:12:12AM +0900, Tetsuo Handa wrote:
> >> On 2023/02/05 0:34, Alan Stern wrote:
> >> Lockdep validation on dev->mutex being disabled is really annoying, and
> >> I want to make lockdep validation on dev->mutex enabled; that is the
> >> "drivers/core: Remove lockdep_set_novalidate_class() usage" patch.
> > 
> >> Even if it is always safe to acquire a child device's lock while holding
> >> the parent's lock, disabling lockdep checks completely on device's lock is
> >> not safe.
> > 
> > I understand the problem you want to solve, and I understand that it
> > can be frustrating.  However, I do not believe you will be able to
> > solve this problem.
> 
> That is a declaration that driver developers are allowed to take it for granted
> that driver callback functions can behave as if dev->mutex is not held. 

No it isn't.  It is a declaration that driver developers must be extra 
careful because lockdep is unable to detect locking errors involving 
dev->mutex.

> Some developers test their changes with lockdep enabled, and believe that their
> changes are correct because lockdep did not complain.
> https://syzkaller.appspot.com/bug?extid=9ef743bba3a17c756174 is an example.

How do you know developers are making this mistake?  That example 
doesn't show anything of the sort; the commit which introduced the bug 
says nothing about lockdep.

> We should somehow update driver core code to make it possible to keep lockdep
> checks enabled on dev->mutex.

I'm sorry, but that simply is not feasible.  It doesn't matter how much 
you want to do it or feel it is needed; there is no reasonable way to do 
it.  To take just one example, what you are saying implies that when a 
driver is probed for a device, it would not be allowed to register a 
child device.  That's a ridiculous restriction.

(I might also mention that dev->mutex is used by drivers in places 
outside of the driver core.  So even if you did magically manage to fix 
the driver core, the problem would still remain.)

Alan Stern

Re: Converting dev->mutex into dev->spinlock ?

[Linus Torvalds]

On Sat, Feb 4, 2023 at 12:01 PM Alan Stern <stern@rowland.harvard.edu> wrote:
>
> I'm sorry, but that simply is not feasible.  It doesn't matter how much
> you want to do it or feel it is needed; there is no reasonable way to do
> it.  To take just one example, what you are saying implies that when a
> driver is probed for a device, it would not be allowed to register a
> child device.  That's a ridiculous restriction.

Well, we've worked around that in other places by making the lockdep
classes for different locks of the same type be different.

So this *could* possibly be solved by lockdep being smarter about
dev->mutex than just "disable checking entirely".

So maybe the lock_set_novalidate_class() could be something better. It
_is_ kind of disgusting.

That said, maybe people tried to subclass the locks and failed, and
that "no validation" is the best that can be done.

But other areas *do* end up spending extra effort to separate out the
locks (and the different uses of the locks), and I think the
dev->mutex is one of the few cases that just gives up and says "no
validation at all".

The other case seems to be the md bcache code.

                  Linus

Re: Converting dev->mutex into dev->spinlock ?

[Hillf Danton]

On Sat, 4 Feb 2023 10:40:52 -0500 Alan Stern <stern@rowland.harvard.edu>
> On Sun, Feb 05, 2023 at 12:30:07AM +0900, Tetsuo Handa wrote:
> > On 2023/02/05 0:12, Alan Stern wrote:
> > >>  it would solve many deadlocks in driver code if you can update
> > > 
> > > What deadlocks?  If there are so many deadlocks floating around in 
> > > driver code, why haven't we heard about them before now?
> > 
> > Since dev->mutex is hidden from lockdep checks, nobody can see lockdep warnings.
> > syzbot is reporting real deadlocks without lockdep warnings, for the fundamental
> > problem you mentioned in https://lkml.kernel.org/r/Pine.LNX.4.44L0.0804171117450.18040-100000@iolanthe.rowland.org
> > is remaining. I'm suggesting you that now is time to address this fundamental problem.
> 
> Maybe so.  But the place to address it is inside lockdep, not in the 
> driver core.
> 
> > >> (by e.g. replacing dev->mutex with dev->spinlock and dev->atomic_flags).
> > >> But I'm not familiar enough to propose such change...
> > > 
> > > Such a change cannot be made.  Consider this: Driver callbacks often
> > > need to sleep.  But when a thread holds a spinlock, it is not allowed to 
> > > sleep.  Therefore driver callbacks must not be invoked while a spinlock 
> > > is held.
> > 
> > What I'm suggesting is "Do not call driver callbacks with dev->mutex held,
> > by rewriting driver core code".
> 
> That cannot be done.  The only possible solution is to teach lockdep how 
> to handle recursive locking structures.

It works in dcache - see the slow path in dentry_kill() for instance.

Hillf

Re: Converting dev->mutex into dev->spinlock ?

[Alan Stern]

On Sat, Feb 04, 2023 at 12:14:54PM -0800, Linus Torvalds wrote:
> On Sat, Feb 4, 2023 at 12:01 PM Alan Stern <stern@rowland.harvard.edu> wrote:
> >
> > I'm sorry, but that simply is not feasible.  It doesn't matter how much
> > you want to do it or feel it is needed; there is no reasonable way to do
> > it.  To take just one example, what you are saying implies that when a
> > driver is probed for a device, it would not be allowed to register a
> > child device.  That's a ridiculous restriction.
> 
> Well, we've worked around that in other places by making the lockdep
> classes for different locks of the same type be different.
> 
> So this *could* possibly be solved by lockdep being smarter about
> dev->mutex than just "disable checking entirely".
> 
> So maybe the lock_set_novalidate_class() could be something better. It
> _is_ kind of disgusting.
> 
> That said, maybe people tried to subclass the locks and failed, and
> that "no validation" is the best that can be done.
> 
> But other areas *do* end up spending extra effort to separate out the
> locks (and the different uses of the locks), and I think the
> dev->mutex is one of the few cases that just gives up and says "no
> validation at all".
> 
> The other case seems to be the md bcache code.

I suppose we could create separate lockdep classes for every bus_type 
and device_type combination, as well as for the different sorts of 
devices -- treat things like class devices separately from normal 
devices, and so on.  But even then there would be trouble.

For example, consider PCI devices and PCI bridges (this sort of thing 
happens on other buses too).  I don't know the details of how the PCI 
subsystem works, but presumably when a bridge is probed, the driver then 
probes all the devices on the other side of the bridge while holding the 
bridge's lock.  Then if one of those devices is another bridge, the same 
thing happens recursively, and so on.  How would drivers cope with that?  
How deep will this nesting go?  I doubt that the driver core could take 
care of these issues all by itself.

I don't know if the following situation ever happens anywhere, but it 
could: Suppose a driver wants to lock several children of some device A.  
Providing it already holds A's lock, this is perfectly safe.  But how 
can we tell lockdep?  Even if A belongs to a different lockdep class 
from its children, the children would all be in the same class.

What happens when a driver wants to lock both a regular device and its 
corresponding class device?  Some drivers might acquire the locks in one 
order and some drivers in another.  Again it's safe, because separate 
drivers will never try to lock the same devices, but how do you tell 
lockdep about this?

No doubt there are other examples of potential problems.  Somebody could 
try to implement this kind of approach, but almost certainly it would 
lead to tons of false positives.

Alan Stern

Re: Converting dev->mutex into dev->spinlock ?

[Tetsuo Handa]

On 2023/02/05 5:01, Alan Stern wrote:
> On Sun, Feb 05, 2023 at 02:09:40AM +0900, Tetsuo Handa wrote:
>> On 2023/02/05 1:27, Alan Stern wrote:
>>> On Sun, Feb 05, 2023 at 01:12:12AM +0900, Tetsuo Handa wrote:
>>>> On 2023/02/05 0:34, Alan Stern wrote:
>>>> Lockdep validation on dev->mutex being disabled is really annoying, and
>>>> I want to make lockdep validation on dev->mutex enabled; that is the
>>>> "drivers/core: Remove lockdep_set_novalidate_class() usage" patch.
>>>
>>>> Even if it is always safe to acquire a child device's lock while holding
>>>> the parent's lock, disabling lockdep checks completely on device's lock is
>>>> not safe.
>>>
>>> I understand the problem you want to solve, and I understand that it
>>> can be frustrating.  However, I do not believe you will be able to
>>> solve this problem.
>>
>> That is a declaration that driver developers are allowed to take it for granted
>> that driver callback functions can behave as if dev->mutex is not held. 
> 
> No it isn't.  It is a declaration that driver developers must be extra 
> careful because lockdep is unable to detect locking errors involving 
> dev->mutex.

Driver developers are not always familiar with locks used by driver core,
like your

  It's hard to figure out what's wrong from looking at the syzbot report.
  What makes you think it is connected with dev->mutex?

  At first glance, it seems that the ath6kl driver is trying to flush a
  workqueue while holding a lock or mutex that is needed by one of the
  jobs in the workqueue.  That's obviously never going to work, no matter
  what sort of lockdep validation gets used.

comment indicates that you did not notice that dev->mutex was connected to
this problem which involved ath6kl driver code and ath9k driver code and
driver core code.

Core developers can't assume that driver developers are extra careful, as
well as driver developers can't assume that core developers are familiar
with locks used by individual drivers. We need to fill the gap.

> 
>> Some developers test their changes with lockdep enabled, and believe that their
>> changes are correct because lockdep did not complain.
>> https://syzkaller.appspot.com/bug?extid=9ef743bba3a17c756174 is an example.
> 
> How do you know developers are making this mistake?  That example 
> doesn't show anything of the sort; the commit which introduced the bug 
> says nothing about lockdep.

The commit which introduced the bug cannot say something about lockdep, for
lockdep validation is disabled and nobody noticed the possibility of deadlock
until syzbot reports it as hung. Since the possibility of deadlock cannot be
noticed until syzbot reports it as hung, I assume that there are many similar
deadlocks in the kernel that involves dev->mutex. How do you teach developers
that they are making this mistake, without keeping lockdep validation enabled?

By keeping lockdep validation disabled, you are declaring that driver developers
need not to worry about dev->mutex rather than declaring that driver developers
need to worry about dev->mutex.

Re: Converting dev->mutex into dev->spinlock ?

[Alan Stern]

On Sun, Feb 05, 2023 at 10:31:56AM +0900, Tetsuo Handa wrote:
> On 2023/02/05 5:01, Alan Stern wrote:
> > On Sun, Feb 05, 2023 at 02:09:40AM +0900, Tetsuo Handa wrote:
> >> That is a declaration that driver developers are allowed to take it for granted
> >> that driver callback functions can behave as if dev->mutex is not held. 
> > 
> > No it isn't.  It is a declaration that driver developers must be extra 
> > careful because lockdep is unable to detect locking errors involving 
> > dev->mutex.
> 
> Driver developers are not always familiar with locks used by driver core,
> like your
> 
>   It's hard to figure out what's wrong from looking at the syzbot report.
>   What makes you think it is connected with dev->mutex?

You didn't answer this question.

>   At first glance, it seems that the ath6kl driver is trying to flush a
>   workqueue while holding a lock or mutex that is needed by one of the
>   jobs in the workqueue.  That's obviously never going to work, no matter
>   what sort of lockdep validation gets used.
> 
> comment indicates that you did not notice that dev->mutex was connected to
> this problem which involved ath6kl driver code and ath9k driver code and
> driver core code.

Of course I didn't.  There isn't enough information in the syzbot log 
for someone to recognize the connection if they aren't already familiar 
with the code in question.

> Core developers can't assume that driver developers are extra careful, as
> well as driver developers can't assume that core developers are familiar
> with locks used by individual drivers. We need to fill the gap.

Agreed.

> >> Some developers test their changes with lockdep enabled, and believe that their
> >> changes are correct because lockdep did not complain.
> >> https://syzkaller.appspot.com/bug?extid=9ef743bba3a17c756174 is an example.
> > 
> > How do you know developers are making this mistake?  That example 
> > doesn't show anything of the sort; the commit which introduced the bug 
> > says nothing about lockdep.
> 
> The commit which introduced the bug cannot say something about lockdep, for
> lockdep validation is disabled and nobody noticed the possibility of deadlock
> until syzbot reports it as hung. Since the possibility of deadlock cannot be
> noticed until syzbot reports it as hung,

That isn't true at all.  There are lots of occasions when people realize 
that a deadlock might occur without seeing a report from lockdep or 
syzbot.  You just aren't aware of these occasions because the developer 
then fixes the code before submitting it.  But if you search through the 
mailing list archives, I'm sure you'll find plenty of examples where 
somebody criticizes a proposed patch on the grounds that it can cause a 
deadlock.

>  I assume that there are many similar
> deadlocks in the kernel that involves dev->mutex. How do you teach developers
> that they are making this mistake, without keeping lockdep validation enabled?

There probably are many similar deadlocks in the kernel.  There probably 
also are deadlocks (not involving dev->mutex) which lockdep could catch, 
but hasn't because the right combination of conditions hasn't occurred.

You teach developers about this the same way you teach them about 
anything else: Publishing information, talking to people, and putting 
comments in the kernel source code.

> By keeping lockdep validation disabled, you are declaring that driver developers
> need not to worry about dev->mutex rather than declaring that driver developers
> need to worry about dev->mutex.

That is a very peculiar thing to say.  How do you think people managed 
to deal with deadlocks in the kernel before lockdep was developed?  Do 
you think they said: "My testing didn't reveal any deadlocks, so the 
code must be perfect"?

Of course they didn't.  And now people simply need to realize that 
lockdep isn't perfect either.

And by the way, by disabling lockdep validation I am declaraing that 
enabling it would cause an overwhelming number of false positives, 
rendering lockdep useless (as you found out when you tried).  Not that 
driver developers don't have to worry about dev->mutex.

Alan Stern

Re: Converting dev->mutex into dev->spinlock ?

[Hillf Danton]

On Sun, 5 Feb 2023 11:46:06 -0500 Alan Stern <stern@rowland.harvard.edu>
> 
> And by the way, by disabling lockdep validation I am declaraing that 
> enabling it would cause an overwhelming number of false positives, 

Could you share 5 false positives you see upstream to help understand how
it is useless?

Hillf

> rendering lockdep useless (as you found out when you tried).  Not that 
> driver developers don't have to worry about dev->mutex.
> 
> Alan Stern

Re: Converting dev->mutex into dev->spinlock ?

[Matthew Wilcox]

On Mon, Feb 06, 2023 at 10:56:29AM +0800, Hillf Danton wrote:
> On Sun, 5 Feb 2023 11:46:06 -0500 Alan Stern <stern@rowland.harvard.edu>
> > 
> > And by the way, by disabling lockdep validation I am declaraing that 
> > enabling it would cause an overwhelming number of false positives, 
> 
> Could you share 5 false positives you see upstream to help understand how
> it is useless?

I've asked you before to stop cc'ing linux-mm on things which aren't
about memory management.  Now I'm asking you publically.

Re: Converting dev->mutex into dev->spinlock ?

[Greg Kroah-Hartman]

On Mon, Feb 06, 2023 at 10:56:29AM +0800, Hillf Danton wrote:
> On Sun, 5 Feb 2023 11:46:06 -0500 Alan Stern <stern@rowland.harvard.edu>
> > 
> > And by the way, by disabling lockdep validation I am declaraing that 
> > enabling it would cause an overwhelming number of false positives, 
> 
> Could you share 5 false positives you see upstream to help understand how
> it is useless?

Please see this other email in this thread:
	https://lore.kernel.org/r/Y98FLlr7jkiFlV0k@rowland.harvard.edu

Re: Converting dev->mutex into dev->spinlock ?

[Hillf Danton]

On Mon, 6 Feb 2023 06:17:03 +0100 Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> On Mon, Feb 06, 2023 at 10:56:29AM +0800, Hillf Danton wrote:
> > On Sun, 5 Feb 2023 11:46:06 -0500 Alan Stern <stern@rowland.harvard.edu>
> > > 
> > > And by the way, by disabling lockdep validation I am declaraing that 
> > > enabling it would cause an overwhelming number of false positives, 
> > 
> > Could you share 5 false positives you see upstream to help understand how
> > it is useless?
> 
> Please see this other email in this thread:
> 	https://lore.kernel.org/r/Y98FLlr7jkiFlV0k@rowland.harvard.edu

What lockdep warnings?  Specific examples, please.

Re: Converting dev->mutex into dev->spinlock ?

[Greg Kroah-Hartman]

On Mon, Feb 06, 2023 at 02:43:05PM +0800, Hillf Danton wrote:
> On Mon, 6 Feb 2023 06:17:03 +0100 Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> > On Mon, Feb 06, 2023 at 10:56:29AM +0800, Hillf Danton wrote:
> > > On Sun, 5 Feb 2023 11:46:06 -0500 Alan Stern <stern@rowland.harvard.edu>
> > > > 
> > > > And by the way, by disabling lockdep validation I am declaraing that 
> > > > enabling it would cause an overwhelming number of false positives, 
> > > 
> > > Could you share 5 false positives you see upstream to help understand how
> > > it is useless?
> > 
> > Please see this other email in this thread:
> > 	https://lore.kernel.org/r/Y98FLlr7jkiFlV0k@rowland.harvard.edu
> 
> What lockdep warnings?  Specific examples, please.

Remove the one line of code, as per the patch in this thread, and boot
with lockdep enabled and see what happens if you wish to see them
yourself.

thanks,

greg k-h

Re: Converting dev->mutex into dev->spinlock ?

[Tetsuo Handa]

On 2023/02/05 10:23, Alan Stern wrote:
> I suppose we could create separate lockdep classes for every bus_type 
> and device_type combination, as well as for the different sorts of 
> devices -- treat things like class devices separately from normal 
> devices, and so on.  But even then there would be trouble.

Sorry, since I'm not familiar with devices, I can't interpret what you
are talking about in this response. But why don't you try test5() approach
in an example module shown below (i.e. treat all dev->mutex instances
independent to each other) ?

Sharing mutex_init() (like test2() approach) causes false positives,
but allocating a key on each dev->mutex (like test5() approach) should
avoid false positives.

----------
#include <linux/module.h>
#include <linux/slab.h>

static struct mutex *alloc_mutex(void)
{
	return kzalloc(sizeof(struct mutex), GFP_KERNEL | __GFP_NOFAIL);
}

static void free_mutex(struct mutex *m)
{
	kfree(m);
}

static void test1(void)
{
	struct mutex *parent_mutex;
	struct mutex *peer_mutex[4];
	int i;

	pr_info("Running %s\n", __func__);
	parent_mutex = alloc_mutex();
	mutex_init(parent_mutex);

	peer_mutex[0] = alloc_mutex();
	mutex_init(peer_mutex[0]);
	peer_mutex[1] = alloc_mutex();
	mutex_init(peer_mutex[1]);
	peer_mutex[2] = alloc_mutex();
	mutex_init(peer_mutex[2]);
	peer_mutex[3] = alloc_mutex();
	mutex_init(peer_mutex[3]);

	mutex_lock(parent_mutex);
	for (i = 0; i < 4; i++)
		mutex_lock(peer_mutex[i]);
	for (i = 0; i < 4; i++)
		mutex_unlock(peer_mutex[i]);
	mutex_unlock(parent_mutex);
	for (i = 0; i < 4; i++)
		free_mutex(peer_mutex[i]);
	free_mutex(parent_mutex);
}

static void test2(void)
{
	struct mutex *parent_mutex;
	struct mutex *peer_mutex[4];
	int i;

	pr_info("Running %s\n", __func__);
	parent_mutex = alloc_mutex();
	mutex_init(parent_mutex);
	for (i = 0; i < 4; i++) {
		peer_mutex[i] = alloc_mutex();
		mutex_init(peer_mutex[i]);
	}
	mutex_lock(parent_mutex);
	for (i = 0; i < 4; i++)
		mutex_lock(peer_mutex[i]);
	for (i = 0; i < 4; i++)
		mutex_unlock(peer_mutex[i]);
	mutex_unlock(parent_mutex);
	for (i = 0; i < 4; i++)
		free_mutex(peer_mutex[i]);
	free_mutex(parent_mutex);
}

static void test3(void)
{
	struct mutex *parent_mutex;
	struct mutex *peer_mutex[4];
	int i;

	pr_info("Running %s\n", __func__);
	parent_mutex = alloc_mutex();
	mutex_init(parent_mutex);
	for (i = 0; i < 4; i++) {
		peer_mutex[i] = alloc_mutex();
		switch (i) {
		case 0:
			mutex_init(peer_mutex[i]);
			break;
		case 1:
			mutex_init(peer_mutex[i]);
			break;
		case 2:
			mutex_init(peer_mutex[i]);
			break;
		case 3:
			mutex_init(peer_mutex[i]);
			break;
		}
	}
	mutex_lock(parent_mutex);
	for (i = 0; i < 4; i++)
		mutex_lock(peer_mutex[i]);
	for (i = 0; i < 4; i++)
		mutex_unlock(peer_mutex[i]);
	mutex_unlock(parent_mutex);
	for (i = 0; i < 4; i++)
		free_mutex(peer_mutex[i]);
	free_mutex(parent_mutex);
}

static void test4(void)
{
	struct mutex *parent_mutex;
	struct mutex *peer_mutex[4];
	int i;

	pr_info("Running %s\n", __func__);
	parent_mutex = alloc_mutex();
	mutex_init(parent_mutex);
	for (i = 0; i < 4; i++) {
		peer_mutex[i] = alloc_mutex();
		switch (i) {
		case 0:
			mutex_init(peer_mutex[i]);
			break;
		case 1:
			mutex_init(peer_mutex[i]);
			break;
		case 2:
			mutex_init(peer_mutex[i]);
			break;
		case 3:
			mutex_init(peer_mutex[i]);
			break;
		}
	}
	mutex_lock(parent_mutex);
	for (i = 0; i < 4; i++)
		mutex_lock(peer_mutex[i]);
	for (i = 0; i < 4; i++)
		mutex_unlock(peer_mutex[i]);
	for (i = 3; i >= 0; i--)
		mutex_lock(peer_mutex[i]);
	for (i = 3; i >= 0; i--)
		mutex_unlock(peer_mutex[i]);
	mutex_unlock(parent_mutex);
	for (i = 0; i < 4; i++)
		free_mutex(peer_mutex[i]);
	free_mutex(parent_mutex);
}

struct mutex2 {
	struct mutex mutex;
	struct lock_class_key key;
};

static struct mutex2 *alloc_mutex2(void)
{
	struct mutex2 *m = kzalloc(sizeof(struct mutex2), GFP_KERNEL | __GFP_NOFAIL);

	lockdep_register_key(&m->key);
	mutex_init(&m->mutex);
	lockdep_set_class(&m->mutex, &m->key);
	return m;
}

static void free_mutex2(struct mutex2 *m)
{
	mutex_destroy(&m->mutex);
	lockdep_unregister_key(&m->key);
	kfree(m);
}

static void test5(void)
{
	struct mutex2 *parent_mutex;
	struct mutex2 *peer_mutex[4];
	int i;

	pr_info("Running %s\n", __func__);
	parent_mutex = alloc_mutex2();
	for (i = 0; i < 4; i++)
		peer_mutex[i] = alloc_mutex2();
	mutex_lock(&parent_mutex->mutex);
	for (i = 0; i < 4; i++)
		mutex_lock(&peer_mutex[i]->mutex);
	for (i = 0; i < 4; i++)
		mutex_unlock(&peer_mutex[i]->mutex);
	mutex_unlock(&parent_mutex->mutex);
	for (i = 0; i < 4; i++)
		free_mutex2(peer_mutex[i]);
	free_mutex2(parent_mutex);
}

static void test6(void)
{
	struct mutex2 *parent_mutex;
	struct mutex2 *peer_mutex[4];
	int i;

	pr_info("Running %s\n", __func__);
	parent_mutex = alloc_mutex2();
	for (i = 0; i < 4; i++)
		peer_mutex[i] = alloc_mutex2();
	mutex_lock(&parent_mutex->mutex);
	for (i = 0; i < 4; i++)
		mutex_lock(&peer_mutex[i]->mutex);
	for (i = 0; i < 4; i++)
		mutex_unlock(&peer_mutex[i]->mutex);
	for (i = 3; i >= 0; i--)
		mutex_lock(&peer_mutex[i]->mutex);
	for (i = 3; i >= 0; i--)
		mutex_unlock(&peer_mutex[i]->mutex);
	mutex_unlock(&parent_mutex->mutex);
	for (i = 0; i < 4; i++)
		free_mutex2(peer_mutex[i]);
	free_mutex2(parent_mutex);
}

static int __init lockdep_test_init(void)
{
	if (1)
		test1(); // safe and lockdep does not complain
	if (0)
		test2(); // safe but lockdep complains
	if (1)
		test3(); // safe and lockdep does not complain
	if (0)
		test4(); // unsafe and lockdep complains
	if (1)
		test5(); // safe and lockdep does not complain
	if (0)
		test6(); // unsafe and lockdep complains
        return -EINVAL;
}

module_init(lockdep_test_init);
MODULE_LICENSE("GPL");
----------

Re: Converting dev->mutex into dev->spinlock ?

[Alan Stern]

On Mon, Feb 06, 2023 at 11:13:38PM +0900, Tetsuo Handa wrote:
> On 2023/02/05 10:23, Alan Stern wrote:
> > I suppose we could create separate lockdep classes for every bus_type 
> > and device_type combination, as well as for the different sorts of 
> > devices -- treat things like class devices separately from normal 
> > devices, and so on.  But even then there would be trouble.
> 
> Sorry, since I'm not familiar with devices, I can't interpret what you
> are talking about in this response. But why don't you try test5() approach
> in an example module shown below (i.e. treat all dev->mutex instances
> independent to each other) ?
> 
> Sharing mutex_init() (like test2() approach) causes false positives,
> but allocating a key on each dev->mutex (like test5() approach) should
> avoid false positives.

Interesting idea.  I'm doubtful that it will accomplish all that you 
want.  After all, one of lockdep's biggest advantages is that it can 
detect the potential for deadlocks without a deadlock actually 
occurring.  By putting each mutex into its own class, you lose much of 
this ability.

But who knows?  Maybe it will be a big help.

Anyway, below is a patch you can try, based on the code for your test5.  
Let me know what happens.

Alan Stern


Index: usb-devel/drivers/base/core.c
===================================================================
--- usb-devel.orig/drivers/base/core.c
+++ usb-devel/drivers/base/core.c
@@ -2322,6 +2322,8 @@ static void device_release(struct kobjec
 	devres_release_all(dev);
 
 	kfree(dev->dma_range_map);
+	mutex_destroy(&dev->mutex);
+	lockdep_unregister_key(&dev->mutex_key);
 
 	if (dev->release)
 		dev->release(dev);
@@ -2941,7 +2943,8 @@ 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);
+	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;

Re: Converting dev->mutex into dev->spinlock ?

[Tetsuo Handa]

On 2023/02/07 0:45, Alan Stern wrote:
> On Mon, Feb 06, 2023 at 11:13:38PM +0900, Tetsuo Handa wrote:
>> On 2023/02/05 10:23, Alan Stern wrote:
>>> I suppose we could create separate lockdep classes for every bus_type 
>>> and device_type combination, as well as for the different sorts of 
>>> devices -- treat things like class devices separately from normal 
>>> devices, and so on.  But even then there would be trouble.
>>
>> Sorry, since I'm not familiar with devices, I can't interpret what you
>> are talking about in this response. But why don't you try test5() approach
>> in an example module shown below (i.e. treat all dev->mutex instances
>> independent to each other) ?
>>
>> Sharing mutex_init() (like test2() approach) causes false positives,
>> but allocating a key on each dev->mutex (like test5() approach) should
>> avoid false positives.
> 
> Interesting idea.  I'm doubtful that it will accomplish all that you 
> want.  After all, one of lockdep's biggest advantages is that it can 
> detect the potential for deadlocks without a deadlock actually 
> occurring.  By putting each mutex into its own class, you lose much of 
> this ability.
> 
> But who knows?  Maybe it will be a big help.
> 
> Anyway, below is a patch you can try, based on the code for your test5.  
> Let me know what happens.
> 

It boots, except lockdep_register_key() hit WARN_ON_ONCE() at
device_register(&platform_bus) from platform_bus_init(), for
platform_bus is a static object.

  struct device platform_bus = {
  	.init_name	= "platform",
  };

We need to skip lockdep_register_key()/lockdep_unregister_key() on
static "struct device" instances...

----------
[    0.550046][    T1] smpboot: Total of 12 processors activated (74513.31 BogoMIPS)
[    0.559082][    T1] devtmpfs: initialized
[    0.560054][    T1] ------------[ cut here ]------------
[    0.562046][    T1] WARNING: CPU: 0 PID: 1 at kernel/locking/lockdep.c:1223 lockdep_register_key+0x1a2/0x230
[    0.564046][    T1] Modules linked in:
[    0.565050][    T1] CPU: 0 PID: 1 Comm: swapper/0 Not tainted 6.2.0-rc7+ #16
[    0.567046][    T1] Hardware name: VMware, Inc. VMware Virtual Platform/440BX Desktop Reference Platform, BIOS 6.00 11/12/2020
[    0.569077][    T1] RIP: 0010:lockdep_register_key+0x1a2/0x230
[    0.571046][    T1] Code: 89 03 4a 89 1c e5 60 b1 e8 84 48 85 c0 0f 84 27 ff ff ff 8b 3d c7 68 f8 01 48 89 58 08 85 ff 0f 85 54 ff ff ff e9 1a ff ff ff <0f> 0b 5b 41 5c 41 5d 41 5e 5d c3 89 c6 48 c7 c7 70 41 05 85 e8 35
[    0.573046][    T1] RSP: 0000:ffffadbb00017e80 EFLAGS: 00010202
[    0.575046][    T1] RAX: 0000000000000001 RBX: ffffffff8443f5d0 RCX: 0000000000000000
[    0.577054][    T1] RDX: 0000000000000001 RSI: 0000000000000001 RDI: ffffffff8443f5d0
[    0.579069][    T1] RBP: ffffadbb00017ea0 R08: 0000000000000003 R09: 0000000000000000
[    0.581069][    T1] R10: d6bf87c490213bdc R11: 0000000000000001 R12: ffffffff8443f5d0
[    0.583069][    T1] R13: 0000000000000000 R14: 0000000000000000 R15: 0000000000000000
[    0.585058][    T1] FS:  0000000000000000(0000) GS:ffff9b7ef6e00000(0000) knlGS:0000000000000000
[    0.587046][    T1] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[    0.589046][    T1] CR2: ffff9b7df0202000 CR3: 000000012f011001 CR4: 0000000000370ef0
[    0.591046][    T1] Call Trace:
[    0.592310][    T1]  <TASK>
[    0.594046][    T1]  device_initialize+0x5f/0x170
[    0.595046][    T1]  device_register+0xd/0x20
[    0.597046][    T1]  platform_bus_init+0x16/0x4d
[    0.598061][    T1]  driver_init+0x2e/0x3a
[    0.600054][    T1]  kernel_init_freeable+0xc3/0x1d2
[    0.601051][    T1]  ? rest_init+0x190/0x190
[    0.603051][    T1]  kernel_init+0x15/0x120
[    0.604273][    T1]  ret_from_fork+0x1f/0x30
[    0.606058][    T1]  </TASK>
[    0.607069][    T1] irq event stamp: 38345
[    0.608284][    T1] hardirqs last  enabled at (38357): [<ffffffff830d9953>] __up_console_sem+0x53/0x60
[    0.610046][    T1] hardirqs last disabled at (38370): [<ffffffff830d9938>] __up_console_sem+0x38/0x60
[    0.613054][    T1] softirqs last  enabled at (38314): [<ffffffff838d54db>] __do_softirq+0x30b/0x46f
[    0.615061][    T1] softirqs last disabled at (38309): [<ffffffff8306e859>] irq_exit_rcu+0xb9/0xf0
[    0.617059][    T1] ---[ end trace 0000000000000000 ]---
[    0.622102][    T1] ACPI: PM: Registering ACPI NVS region [mem 0xbfeff000-0xbfefffff] (4096 bytes)
[    0.625130][    T1] clocksource: jiffies: mask: 0xffffffff max_cycles: 0xffffffff, max_idle_ns: 1911260446275000 ns
----------

Re: Converting dev->mutex into dev->spinlock ?

[Alan Stern]

On Tue, Feb 07, 2023 at 10:07:18PM +0900, Tetsuo Handa wrote:
> On 2023/02/07 0:45, Alan Stern wrote:
> > On Mon, Feb 06, 2023 at 11:13:38PM +0900, Tetsuo Handa wrote:
> >> On 2023/02/05 10:23, Alan Stern wrote:
> >>> I suppose we could create separate lockdep classes for every bus_type 
> >>> and device_type combination, as well as for the different sorts of 
> >>> devices -- treat things like class devices separately from normal 
> >>> devices, and so on.  But even then there would be trouble.
> >>
> >> Sorry, since I'm not familiar with devices, I can't interpret what you
> >> are talking about in this response. But why don't you try test5() approach
> >> in an example module shown below (i.e. treat all dev->mutex instances
> >> independent to each other) ?
> >>
> >> Sharing mutex_init() (like test2() approach) causes false positives,
> >> but allocating a key on each dev->mutex (like test5() approach) should
> >> avoid false positives.
> > 
> > Interesting idea.  I'm doubtful that it will accomplish all that you 
> > want.  After all, one of lockdep's biggest advantages is that it can 
> > detect the potential for deadlocks without a deadlock actually 
> > occurring.  By putting each mutex into its own class, you lose much of 
> > this ability.
> > 
> > But who knows?  Maybe it will be a big help.
> > 
> > Anyway, below is a patch you can try, based on the code for your test5.  
> > Let me know what happens.
> > 
> 
> It boots, except lockdep_register_key() hit WARN_ON_ONCE() at
> device_register(&platform_bus) from platform_bus_init(), for
> platform_bus is a static object.
> 
>   struct device platform_bus = {
>   	.init_name	= "platform",
>   };
> 
> We need to skip lockdep_register_key()/lockdep_unregister_key() on
> static "struct device" instances...

Okay, no doubt you can modify the patch to handle that.

The real question is what will happen in your syzbot test scenarios.  
Lockdep certainly ought to be able to detect a real deadlock when one 
occurs.  It will be more interesting to find out if it can warn about 
potential deadlocks _without_ them occurring.

Alan Stern

Re: Converting dev->mutex into dev->spinlock ?

[Tetsuo Handa]

On 2023/02/08 2:46, Alan Stern wrote:
> The real question is what will happen in your syzbot test scenarios.  
> Lockdep certainly ought to be able to detect a real deadlock when one 
> occurs.  It will be more interesting to find out if it can warn about 
> potential deadlocks _without_ them occurring.

For example, https://syzkaller.appspot.com/x/repro.c?x=15556074480000 generates
below warning, but I don't have syzbot environment. Please propose an updated
patch (which won't hit WARN_ON_ONCE()) for allowing people to try it in syzbot
environment.

----------
[  122.946483][ T3692] 
[  122.979855][ T3692] ======================================================
[  122.984206][ T3692] WARNING: possible circular locking dependency detected
[  122.986920][ T3692] 6.2.0-rc7-00011-g05ecb680708a-dirty #943 Tainted: G        W         
[  122.989918][ T3692] ------------------------------------------------------
[  122.993357][ T3692] a.out/3692 is trying to acquire lock:
[  122.995732][ T3692] ffff888128168900 (&dev->mutex_key#165){+.+.}-{3:3}, at: nfc_dev_down+0x26/0x120
[  123.008266][ T3692] 
[  123.008266][ T3692] but task is already holding lock:
[  123.010995][ T3692] ffffffff85a09040 (rfkill_global_mutex){+.+.}-{3:3}, at: rfkill_fop_write+0x10e/0x360
[  123.020389][ T3692] 
[  123.020389][ T3692] which lock already depends on the new lock.
[  123.020389][ T3692] 
[  123.029714][ T3692] 
[  123.029714][ T3692] the existing dependency chain (in reverse order) is:
[  123.033255][ T3692] 
[  123.033255][ T3692] -> #1 (rfkill_global_mutex){+.+.}-{3:3}:
[  123.037794][ T3692]        __mutex_lock_common+0xe6/0xea0
[  123.040845][ T3692]        mutex_lock_nested+0x1b/0x20
[  123.043990][ T3692]        rfkill_register+0x25/0x3d0
[  123.046100][ T3692]        nfc_register_device+0xd9/0x200
[  123.048369][ T3692]        nfcsim_device_new+0x146/0x2c0
[  123.077246][ T3692]        nfcsim_init+0x71/0x130
[  123.079456][ T3692]        do_one_initcall+0xab/0x200
[  123.081584][ T3692]        do_initcall_level+0xd7/0x1c0
[  123.084613][ T3692]        do_initcalls+0x3f/0x80
[  123.087020][ T3692]        kernel_init_freeable+0x230/0x2e0
[  123.089388][ T3692]        kernel_init+0x1b/0x290
[  123.091567][ T3692]        ret_from_fork+0x1f/0x30
[  123.094393][ T3692] 
[  123.094393][ T3692] -> #0 (&dev->mutex_key#165){+.+.}-{3:3}:
[  123.097522][ T3692]        __lock_acquire+0x170d/0x33c0
[  123.100739][ T3692]        lock_acquire+0xd3/0x200
[  123.103840][ T3692]        __mutex_lock_common+0xe6/0xea0
[  123.106366][ T3692]        mutex_lock_nested+0x1b/0x20
[  123.108942][ T3692]        nfc_dev_down+0x26/0x120
[  123.111542][ T3692]        nfc_rfkill_set_block+0x26/0x80
[  123.114113][ T3692]        rfkill_set_block+0xa1/0x1e0
[  123.116739][ T3692]        rfkill_fop_write+0x2e9/0x360
[  123.148674][ T3692]        vfs_write+0x187/0x4d0
[  123.151862][ T3692]        ksys_write+0xc6/0x170
[  123.156763][ T3692]        do_syscall_64+0x41/0x90
[  123.161519][ T3692]        entry_SYSCALL_64_after_hwframe+0x46/0xb0
[  123.171373][ T3692] 
[  123.171373][ T3692] other info that might help us debug this:
[  123.171373][ T3692] 
[  123.179398][ T3692]  Possible unsafe locking scenario:
[  123.179398][ T3692] 
[  123.183031][ T3692]        CPU0                    CPU1
[  123.188115][ T3692]        ----                    ----
[  123.190123][ T3692]   lock(rfkill_global_mutex);
[  123.192104][ T3692]                                lock(&dev->mutex_key#165);
[  123.200840][ T3692]                                lock(rfkill_global_mutex);
[  123.207386][ T3692]   lock(&dev->mutex_key#165);
[  123.241397][ T3692] 
[  123.241397][ T3692]  *** DEADLOCK ***
[  123.241397][ T3692] 
[  123.245893][ T3692] 1 lock held by a.out/3692:
[  123.250422][ T3692]  #0: ffffffff85a09040 (rfkill_global_mutex){+.+.}-{3:3}, at: rfkill_fop_write+0x10e/0x360
[  123.256266][ T3692] 
[  123.256266][ T3692] stack backtrace:
[  123.258802][ T3692] CPU: 0 PID: 3692 Comm: a.out Tainted: G        W          6.2.0-rc7-00011-g05ecb680708a-dirty #943
[  123.276931][ T3692] Hardware name: innotek GmbH VirtualBox/VirtualBox, BIOS VirtualBox 12/01/2006
[  123.280352][ T3692] Call Trace:
[  123.310882][ T3692]  <TASK>
[  123.312232][ T3692]  dump_stack_lvl+0xfe/0x190
[  123.314278][ T3692]  check_noncircular+0x12e/0x140
[  123.317038][ T3692]  __lock_acquire+0x170d/0x33c0
[  123.320079][ T3692]  ? __lock_acquire+0x65f/0x33c0
[  123.321887][ T3692]  ? __lock_acquire+0x65f/0x33c0
[  123.325643][ T3692]  lock_acquire+0xd3/0x200
[  123.327611][ T3692]  ? nfc_dev_down+0x26/0x120
[  123.331732][ T3692]  ? nfc_dev_down+0x26/0x120
[  123.335510][ T3692]  ? nfc_dev_down+0x26/0x120
[  123.337961][ T3692]  __mutex_lock_common+0xe6/0xea0
[  123.340214][ T3692]  ? nfc_dev_down+0x26/0x120
[  123.347330][ T3692]  ? nfc_dev_down+0x26/0x120
[  123.352194][ T3692]  mutex_lock_nested+0x1b/0x20
[  123.356877][ T3692]  nfc_dev_down+0x26/0x120
[  123.361856][ T3692]  nfc_rfkill_set_block+0x26/0x80
[  123.378236][ T3692]  rfkill_set_block+0xa1/0x1e0
[  123.379954][ T3692]  rfkill_fop_write+0x2e9/0x360
[  123.381693][ T3692]  ? rfkill_fop_read+0x2a0/0x2a0
[  123.406421][ T3692]  vfs_write+0x187/0x4d0
[  123.408119][ T3692]  ? do_user_addr_fault+0x6e1/0x9c0
[  123.410174][ T3692]  ksys_write+0xc6/0x170
[  123.411856][ T3692]  do_syscall_64+0x41/0x90
[  123.426593][ T3692]  entry_SYSCALL_64_after_hwframe+0x46/0xb0
[  123.429725][ T3692] RIP: 0033:0x7fbea991ea3d
[  123.431577][ T3692] Code: 5b 41 5c c3 66 0f 1f 84 00 00 00 00 00 f3 0f 1e fa 48 89 f8 48 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d 01 f0 ff ff 73 01 c3 48 8b 0d c3 a3 0f 00 f7 d8 64 89 01 48
[  123.461942][ T3692] RSP: 002b:00007ffc8e2f63a8 EFLAGS: 00000246 ORIG_RAX: 0000000000000001
[  123.468363][ T3692] RAX: ffffffffffffffda RBX: 00000000000f4240 RCX: 00007fbea991ea3d
[  123.480268][ T3692] RDX: 0000000000000008 RSI: 0000000020000080 RDI: 0000000000000004
[  123.487754][ T3692] RBP: 0000000000000000 R08: 0000000000000060 R09: 0000000000000060
[  123.491003][ T3692] R10: 0000000000000060 R11: 0000000000000246 R12: 00007ffc8e2f6538
[  123.550555][ T3692] R13: 000055cea974c2e0 R14: 00007ffc8e2f63d0 R15: 00007ffc8e2f63c0
[  123.555519][ T3692]  </TASK>
----------

Re: Converting dev->mutex into dev->spinlock ?

[Alan Stern]

On Wed, Feb 08, 2023 at 07:17:20AM +0900, Tetsuo Handa wrote:
> On 2023/02/08 2:46, Alan Stern wrote:
> > The real question is what will happen in your syzbot test scenarios.  
> > Lockdep certainly ought to be able to detect a real deadlock when one 
> > occurs.  It will be more interesting to find out if it can warn about 
> > potential deadlocks _without_ them occurring.
> 
> For example, https://syzkaller.appspot.com/x/repro.c?x=15556074480000 generates
> below warning, but I don't have syzbot environment. Please propose an updated
> patch (which won't hit WARN_ON_ONCE()) for allowing people to try it in syzbot
> environment.

Here is a patch.  I haven't tried to compile it.

Alan Stern



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);
 
Index: usb-devel/kernel/locking/lockdep.c
===================================================================
--- usb-devel.orig/kernel/locking/lockdep.c
+++ usb-devel/kernel/locking/lockdep.c
@@ -831,7 +831,7 @@ static int arch_is_kernel_initmem_freed(
 }
 #endif
 
-static int static_obj(const void *obj)
+int lockdep_static_obj(const void *obj)
 {
 	unsigned long start = (unsigned long) &_stext,
 		      end   = (unsigned long) &_end,
@@ -857,6 +857,7 @@ static int static_obj(const void *obj)
 	 */
 	return is_module_address(addr) || is_module_percpu_address(addr);
 }
+EXPORT_SYMBOL_GPL(lockdep_static_obj);
 #endif
 
 /*
@@ -969,7 +970,7 @@ static bool assign_lock_key(struct lockd
 		lock->key = (void *)can_addr;
 	else if (__is_module_percpu_address(addr, &can_addr))
 		lock->key = (void *)can_addr;
-	else if (static_obj(lock))
+	else if (lockdep_static_obj(lock))
 		lock->key = (void *)lock;
 	else {
 		/* Debug-check: all keys must be persistent! */
@@ -1220,7 +1221,7 @@ void lockdep_register_key(struct lock_cl
 	struct lock_class_key *k;
 	unsigned long flags;
 
-	if (WARN_ON_ONCE(static_obj(key)))
+	if (WARN_ON_ONCE(lockdep_static_obj(key)))
 		return;
 	hash_head = keyhashentry(key);
 
@@ -1246,7 +1247,7 @@ static bool is_dynamic_key(const struct
 	struct lock_class_key *k;
 	bool found = false;
 
-	if (WARN_ON_ONCE(static_obj(key)))
+	if (WARN_ON_ONCE(lockdep_static_obj(key)))
 		return false;
 
 	/*
@@ -1293,7 +1294,7 @@ register_lock_class(struct lockdep_map *
 	if (!lock->key) {
 		if (!assign_lock_key(lock))
 			return NULL;
-	} else if (!static_obj(lock->key) && !is_dynamic_key(lock->key)) {
+	} else if (!lockdep_static_obj(lock->key) && !is_dynamic_key(lock->key)) {
 		return NULL;
 	}
 
@@ -4836,7 +4837,7 @@ void lockdep_init_map_type(struct lockde
 	 * Sanity check, the lock-class key must either have been allocated
 	 * statically or must have been registered as a dynamic key.
 	 */
-	if (!static_obj(key) && !is_dynamic_key(key)) {
+	if (!lockdep_static_obj(key) && !is_dynamic_key(key)) {
 		if (debug_locks)
 			printk(KERN_ERR "BUG: key %px has not been registered!\n", key);
 		DEBUG_LOCKS_WARN_ON(1);
@@ -6335,7 +6336,7 @@ void lockdep_unregister_key(struct lock_
 
 	might_sleep();
 
-	if (WARN_ON_ONCE(static_obj(key)))
+	if (WARN_ON_ONCE(lockdep_static_obj(key)))
 		return;
 
 	raw_local_irq_save(flags);

[PATCH] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Tetsuo Handa]

Commit 1704f47b50b5 ("lockdep: Add novalidate class for dev->mutex
conversion") made it impossible to find real deadlocks unless timing
dependent testings manage to trigger hung task like [1] and [2]. And
lockdep_set_novalidate_class() remained for more than one decade due to
a fear of false positives [3]. But not sharing mutex_init() could make
it possible to find real deadlocks without triggering hung task [4].
Thus, let's assign a unique class key on each "struct device"->mutex.

Link: https://syzkaller.appspot.com/bug?extid=2d6ac90723742279e101 [1]
Link: https://syzkaller.appspot.com/bug?extid=2e39bc6569d281acbcfb [2]
Link: https://lkml.kernel.org/r/Y98FLlr7jkiFlV0k@rowland.harvard.edu [3]
Link: https://lkml.kernel.org/r/827177aa-bb64-87a9-e1af-dfe070744045@I-love.SAKURA.ne.jp [4]
Suggested-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
Co-developed-by: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Alan Stern <stern@rowland.harvard.edu>
Co-developed-by: Hillf Danton <hdanton@sina.com>
Signed-off-by: Hillf Danton <hdanton@sina.com>
Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
---
Hello, syzkaller users.

We made a patch that keeps lockdep validation enabled on "struct dev->mutex".
Will you try this patch and see if this patch causes boot failures and/or
too frequent crashes to continue testing.

 drivers/base/core.c      | 7 ++++++-
 include/linux/device.h   | 1 +
 include/linux/lockdep.h  | 6 ++++++
 kernel/locking/lockdep.c | 7 +++++++
 4 files changed, 20 insertions(+), 1 deletion(-)

diff --git a/drivers/base/core.c b/drivers/base/core.c
index a3e14143ec0c..c30ecbc4d60e 100644
--- a/drivers/base/core.c
+++ b/drivers/base/core.c
@@ -2322,6 +2322,9 @@ static void device_release(struct kobject *kobj)
 	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,9 @@ void device_initialize(struct device *dev)
 	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);
diff --git a/include/linux/device.h b/include/linux/device.h
index 44e3acae7b36..bdaca9f54dc2 100644
--- a/include/linux/device.h
+++ b/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;
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 1f1099dac3f0..5afc999a7e56 100644
--- a/include/linux/lockdep.h
+++ b/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_task(struct task_struct *task)
 # 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)
 {
 }
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index e3375bc40dad..74c0113646f1 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -857,6 +857,13 @@ 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);
+}
+EXPORT_SYMBOL_GPL(lockdep_static_obj);
+
 #endif
 
 /*
-- 
2.34.1

Re: [PATCH] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

On Wed, Feb 08, 2023 at 07:30:25PM +0900, Tetsuo Handa wrote:
> Commit 1704f47b50b5 ("lockdep: Add novalidate class for dev->mutex
> conversion") made it impossible to find real deadlocks unless timing
> dependent testings manage to trigger hung task like [1] and [2]. And
> lockdep_set_novalidate_class() remained for more than one decade due to
> a fear of false positives [3]. But not sharing mutex_init() could make
> it possible to find real deadlocks without triggering hung task [4].
> Thus, let's assign a unique class key on each "struct device"->mutex.
> 
> Link: https://syzkaller.appspot.com/bug?extid=2d6ac90723742279e101 [1]
> Link: https://syzkaller.appspot.com/bug?extid=2e39bc6569d281acbcfb [2]
> Link: https://lkml.kernel.org/r/Y98FLlr7jkiFlV0k@rowland.harvard.edu [3]
> Link: https://lkml.kernel.org/r/827177aa-bb64-87a9-e1af-dfe070744045@I-love.SAKURA.ne.jp [4]
> Suggested-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
> Co-developed-by: Alan Stern <stern@rowland.harvard.edu>
> Signed-off-by: Alan Stern <stern@rowland.harvard.edu>

You must never do this!

I did not put my Signed-off-by: on the patch I sent to you.  I do not 
want it added to that patch or to this one.  You should never put 
somebody else's Signed-off-by: on a patch unless they tell you it's okay 
to do so.

I'm happy to have people test this patch, but I do not want anybody 
think that it is ready to be merged into the kernel.

> Co-developed-by: Hillf Danton <hdanton@sina.com>
> Signed-off-by: Hillf Danton <hdanton@sina.com>
> Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
> ---
> Hello, syzkaller users.
> 
> We made a patch that keeps lockdep validation enabled on "struct dev->mutex".
> Will you try this patch and see if this patch causes boot failures and/or
> too frequent crashes to continue testing.
> 
>  drivers/base/core.c      | 7 ++++++-
>  include/linux/device.h   | 1 +
>  include/linux/lockdep.h  | 6 ++++++
>  kernel/locking/lockdep.c | 7 +++++++
>  4 files changed, 20 insertions(+), 1 deletion(-)
> 
> diff --git a/drivers/base/core.c b/drivers/base/core.c
> index a3e14143ec0c..c30ecbc4d60e 100644
> --- a/drivers/base/core.c
> +++ b/drivers/base/core.c
> @@ -2322,6 +2322,9 @@ static void device_release(struct kobject *kobj)
>  	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,9 @@ void device_initialize(struct device *dev)
>  	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);
> diff --git a/include/linux/device.h b/include/linux/device.h
> index 44e3acae7b36..bdaca9f54dc2 100644
> --- a/include/linux/device.h
> +++ b/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;
> diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> index 1f1099dac3f0..5afc999a7e56 100644
> --- a/include/linux/lockdep.h
> +++ b/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_task(struct task_struct *task)
>  # 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)
>  {
>  }
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index e3375bc40dad..74c0113646f1 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -857,6 +857,13 @@ 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);
> +}
> +EXPORT_SYMBOL_GPL(lockdep_static_obj);

What's the point of adding a new function that just calls the old 
function?  Why not simply rename the old function?

Alan Stern

> +
>  #endif
>  
>  /*
> -- 
> 2.34.1
> 

Re: [PATCH] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Tetsuo Handa]

On 2023/02/09 0:07, Alan Stern wrote:
> On Wed, Feb 08, 2023 at 07:30:25PM +0900, Tetsuo Handa wrote:
>> Commit 1704f47b50b5 ("lockdep: Add novalidate class for dev->mutex
>> conversion") made it impossible to find real deadlocks unless timing
>> dependent testings manage to trigger hung task like [1] and [2]. And
>> lockdep_set_novalidate_class() remained for more than one decade due to
>> a fear of false positives [3]. But not sharing mutex_init() could make
>> it possible to find real deadlocks without triggering hung task [4].
>> Thus, let's assign a unique class key on each "struct device"->mutex.
>>
>> Link: https://syzkaller.appspot.com/bug?extid=2d6ac90723742279e101 [1]
>> Link: https://syzkaller.appspot.com/bug?extid=2e39bc6569d281acbcfb [2]
>> Link: https://lkml.kernel.org/r/Y98FLlr7jkiFlV0k@rowland.harvard.edu [3]
>> Link: https://lkml.kernel.org/r/827177aa-bb64-87a9-e1af-dfe070744045@I-love.SAKURA.ne.jp [4]
>> Suggested-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
>> Co-developed-by: Alan Stern <stern@rowland.harvard.edu>
>> Signed-off-by: Alan Stern <stern@rowland.harvard.edu>
> 
> You must never do this!
> 
> I did not put my Signed-off-by: on the patch I sent to you.  I do not 
> want it added to that patch or to this one.  You should never put 
> somebody else's Signed-off-by: on a patch unless they tell you it's okay 
> to do so.

Did I misuse the Co-developed-by: tag? I added your Signed-off-by: tag because
https://docs.kernel.org/process/submitting-patches.html#when-to-use-acked-by-cc-and-co-developed-by
states that "every Co-developed-by: must be immediately followed by a Signed-off-by:
of the associated co-author."

I don't know whether the Co-developed-by: tag is used only when somebody else takes over
a previously proposed formal patch. I use the Co-developed-by: tag in order to state
developer's contribution when he/she suggested some plain diff but does not propose
that diff as a formal patch with description. Unless changes are proposed as a formal
patch (by somebody), bugs won't be fixed.

> 
> I'm happy to have people test this patch, but I do not want anybody 
> think that it is ready to be merged into the kernel.

People (and build/test bots) won't test changes that are not proposed as
a formal patch with Signed-off-by: tag. As far as I am aware, bot is not
testing plain diff.

I expected you to post a formal patch with your Signed-off-by: tag, but you didn't.
Therefore, I took over. Namely, define a dummy function for CONFIG_LOCKDEP=n case,
apply Hillf's suggestion, and reduce lines changed in kernel/locking/lockdep.c
in order to make the patch smaller and easier to apply the change.

> 
>> Co-developed-by: Hillf Danton <hdanton@sina.com>
>> Signed-off-by: Hillf Danton <hdanton@sina.com>
>> Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
>> ---

>> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
>> index e3375bc40dad..74c0113646f1 100644
>> --- a/kernel/locking/lockdep.c
>> +++ b/kernel/locking/lockdep.c
>> @@ -857,6 +857,13 @@ 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);
>> +}
>> +EXPORT_SYMBOL_GPL(lockdep_static_obj);
> 
> What's the point of adding a new function that just calls the old 
> function?  Why not simply rename the old function?

This makes the patch smaller and easier to apply the change. Of course,
I can update the patch if lockdep developers prefer rename over add.
What I worry is that lockdep developers do not permit static_obj() being
used by non-lockdep code.

Re: [PATCH] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Linus Torvalds]

On Wed, Feb 8, 2023 at 4:23 PM Tetsuo Handa
<penguin-kernel@i-love.sakura.ne.jp> wrote:
>
> Did I misuse the Co-developed-by: tag? I added your Signed-off-by: tag because
> https://docs.kernel.org/process/submitting-patches.html#when-to-use-acked-by-cc-and-co-developed-by
> states that "every Co-developed-by: must be immediately followed by a Signed-off-by:
> of the associated co-author."

That doesn't mean that *You* can add a Signed-off-by:

Nobody can certify sign-off for anybody else. Read the sign-off rules:
you can add your *own* sign-off if the rules hold, but you can't sign
off for somebody else.

The "Co-developed-by: must be immediately followed by a
Signed-off-by:" thing only means that if there are multiple
developers, then ALL DEVELOPERS MUST SIGN OFF.

It absolutely does *NOT* mean that you adding a Co-developed-by means
that you then add a Signed-off-by.

That's like faking somebody else's signature on some paperwork. Never
do that either, and it's hopefully obvious why.

                  Linus

Re: [PATCH] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Tetsuo Handa]

On 2023/02/09 9:46, Linus Torvalds wrote:
> On Wed, Feb 8, 2023 at 4:23 PM Tetsuo Handa
> <penguin-kernel@i-love.sakura.ne.jp> wrote:
>>
>> Did I misuse the Co-developed-by: tag? I added your Signed-off-by: tag because
>> https://docs.kernel.org/process/submitting-patches.html#when-to-use-acked-by-cc-and-co-developed-by
>> states that "every Co-developed-by: must be immediately followed by a Signed-off-by:
>> of the associated co-author."
> 
> That doesn't mean that *You* can add a Signed-off-by:
> 
> Nobody can certify sign-off for anybody else. Read the sign-off rules:
> you can add your *own* sign-off if the rules hold, but you can't sign
> off for somebody else.
> 
> The "Co-developed-by: must be immediately followed by a
> Signed-off-by:" thing only means that if there are multiple
> developers, then ALL DEVELOPERS MUST SIGN OFF.
> 
> It absolutely does *NOT* mean that you adding a Co-developed-by means
> that you then add a Signed-off-by.
> 
> That's like faking somebody else's signature on some paperwork. Never
> do that either, and it's hopefully obvious why.

OK. Then, how to handle a case where a developer suggested a diff but
he/she does not propose that diff as a formal patch?

Hillf is suggesting diffs for many bugs (an example is
https://syzkaller.appspot.com/bug?id=ee93abc9a483645fc0914811af9c12da355a2e3e ),
and some of diffs look reasonable/correct, but Hillf never tries to propose as
a formal patch, and that diff is left forgotten and that bug remains unfixed.

I don't want to steal Hillf's effort. But given that I can't add Co-developed-by:
and Signed-off-by: on behalf of Hillf, how can I propose a formal patch in a way
that preserves Hillf's effort? Is Suggested-by: suitable for this case?

Re: [PATCH] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

On Thu, Feb 09, 2023 at 09:22:39AM +0900, Tetsuo Handa wrote:
> On 2023/02/09 0:07, Alan Stern wrote:
> > I'm happy to have people test this patch, but I do not want anybody 
> > think that it is ready to be merged into the kernel.
> 
> People (and build/test bots) won't test changes that are not proposed as
> a formal patch with Signed-off-by: tag. As far as I am aware, bot is not
> testing plain diff.

People _do_ test changes without a Signed-off-by: tag.  This happens 
with my patches all the time; I don't put Signed-off-by: on a patch 
until I think it is ready to be merged.  If you search through the email 
archives, you'll find examples where people deliberately put a 
"Not-yet-signed-off-by:" tag on a suggested patch.

Syzbot also tests patches without a Signed-off-by: tag.  Here's a recent 
example:

https://lore.kernel.org/linux-usb/Y9wh8dGK6oHSjJQl@rowland.harvard.edu/

> > What's the point of adding a new function that just calls the old 
> > function?  Why not simply rename the old function?
> 
> This makes the patch smaller and easier to apply the change. Of course,

How does it make the patch easier to apply?  With either the original 
version or yours, you apply the patch by doing

	patch -p1 <patchfile

(or a similar git command).  Same command, same amount of difficulty for 
both patches.

> I can update the patch if lockdep developers prefer rename over add.
> What I worry is that lockdep developers do not permit static_obj() being
> used by non-lockdep code.

I worry about that too, and I hoped that Peter Z. would comment on it. 
But if they don't want the function to be exported, they ought to be 
able to suggest an alternative.

Alan Stern

Re: [PATCH] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Tetsuo Handa]

On 2023/02/09 11:26, Alan Stern wrote:
> On Thu, Feb 09, 2023 at 09:22:39AM +0900, Tetsuo Handa wrote:
>> On 2023/02/09 0:07, Alan Stern wrote:
>>> I'm happy to have people test this patch, but I do not want anybody 
>>> think that it is ready to be merged into the kernel.
>>
>> People (and build/test bots) won't test changes that are not proposed as
>> a formal patch with Signed-off-by: tag. As far as I am aware, bot is not
>> testing plain diff.
> 
> People _do_ test changes without a Signed-off-by: tag.  This happens 
> with my patches all the time; I don't put Signed-off-by: on a patch 
> until I think it is ready to be merged.  If you search through the email 
> archives, you'll find examples where people deliberately put a 
> "Not-yet-signed-off-by:" tag on a suggested patch.

That's a cultural difference. I know there are developers who use
"Not-yet-signed-off-by:" tag. But I'm not subscribed to mailing lists
which you are subscribed to. I'm subscribed to linux-security-module, but
I feel that it is quite rare that developers post changes as plain diff
without Signed-off-by: tag, for people prefer to see formal patches than
plain diff. I can see that only David Howells was using Not-yet-signed-off-by:
tag (like https://marc.info/?l=linux-security-module&m=130455572927447 ).

But even with Not-yet-signed-off-by: tag, his patches are formal patches
with description rather than plain diff. Unlike networking subsystem where
patches sometimes get merged before people have time to review/test,
developers in my subscribed mailing lists tend to propose v2, v3, v4...
patches with "Signed-off-by:" tag instead of posting plain diff.

> Syzbot also tests patches without a Signed-off-by: tag.  Here's a recent 
> example:
> 
> https://lore.kernel.org/linux-usb/Y9wh8dGK6oHSjJQl@rowland.harvard.edu/

That's completely different. syzbot is designed to test plain diff via
explict "#syz test:" directive. If "#syz test:" directive is not included,
syzbot does not test your diff.

Do you know any bot which automatically does testing plain diff? I don't know
when bots (or automated systems) test changes, but my guess is that a formal
patch with "Signed-off-by:" tag serves as the directive for bots to test
changes. Maybe we want a directive (e.g. "Test-requested-by:" tag) which
encourages/asks bots (or automated systems) to test patches but does not
want patches to get merged into permanent git trees.

>> I can update the patch if lockdep developers prefer rename over add.
>> What I worry is that lockdep developers do not permit static_obj() being
>> used by non-lockdep code.
> 
> I worry about that too, and I hoped that Peter Z. would comment on it. 
> But if they don't want the function to be exported, they ought to be 
> able to suggest an alternative.

Then, at least we can start without "EXPORT_SYMBOL_GPL(lockdep_static_obj);"
line, for drivers/base/core.c cannot be built as a module.

Since there are already several locations which directly use e.g. _stext symbol,
we would simply duplicate static_obj() into drivers/base/core.c if Peter does
not want to make static_obj() visible to built-in code.



Anyway, despite being posted as a formal patch, it seems that nobody was
interested in manual testing. As far as I tried "#syz test" this patch against
https://syzkaller.appspot.com/bug?extid=9ef743bba3a17c756174 , syzbot kernel
was able to boot. Therefore, I think it is OK to stay for a week whether
this patch causes too frequent crashes to continue using linux-next.git .

Please propose a formal patch to Peter with your "Signed-off-by:" tag...

[PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

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(-)

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
 
 /*

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Linus Torvalds]

On Sat, Feb 11, 2023 at 1:41 PM Alan Stern <stern@rowland.harvard.edu> wrote:
>
> @@ -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);

So I think this is the right thing to do, but I note that while that
lockdep_set_novalidate_class() was "documented" to only be for
'dev->mutex' by scripts/checkpatch.pl, that horrific thing is also
used by md/bcache/btree.c for the mca_bucket_alloc().

Can we *please* get rid of it there too (it was added by the initial
code, and never had any explicit excuse for it), possibly by using the
same model.

And then we could get rid of lockdep_set_novalidate_class() entirely.
That would be a good thing.

Coly/Kent? See

    https://lore.kernel.org/lkml/Y+gLd78vChQERZ6A@rowland.harvard.edu/

for more context, and

    https://lore.kernel.org/all/28a82f50-39d5-a45f-7c7a-57a66cec0741@I-love.SAKURA.ne.jp/

for some history.

                 Linus

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Kent Overstreet]

On 2/11/23 16:51, Linus Torvalds wrote:
> On Sat, Feb 11, 2023 at 1:41 PM Alan Stern <stern@rowland.harvard.edu> wrote:
>>
>> @@ -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);
> 
> So I think this is the right thing to do, but I note that while that
> lockdep_set_novalidate_class() was "documented" to only be for
> 'dev->mutex' by scripts/checkpatch.pl, that horrific thing is also
> used by md/bcache/btree.c for the mca_bucket_alloc().
> 
> Can we *please* get rid of it there too (it was added by the initial
> code, and never had any explicit excuse for it), possibly by using the
> same model.
> 
> And then we could get rid of lockdep_set_novalidate_class() entirely.
> That would be a good thing.

Yeah, what bcache really needs (and presumably dev->mutex as well) is 
just to disable lockdep checking for self-deadlock of that lock type, 
since it's got its own deadlock avoidance and the subclass thing isn't 
good enough.

I've got a patch that should do what we want, replying from my other 
account with it.

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Kent Overstreet]

On Sat, Feb 11, 2023 at 06:06:28PM -0500, Kent Overstreet wrote:
> Yeah, what bcache really needs (and presumably dev->mutex as well) is just
> to disable lockdep checking for self-deadlock of that lock type, since it's
> got its own deadlock avoidance and the subclass thing isn't good enough.
> 
> I've got a patch that should do what we want, replying from my other account
> with it.
-- >8 --
Subject: [PATCH] locking/lockdep: lockdep_set_no_check_recursion()

This adds a method to tell lockdep not to check lock ordering within a
lock class - but to still check lock ordering w.r.t. other lock types.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
---
 include/linux/lockdep.h       |  6 ++++++
 include/linux/lockdep_types.h |  2 +-
 kernel/locking/lockdep.c      | 26 ++++++++++++++++++++++++++
 3 files changed, 33 insertions(+), 1 deletion(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index e027c504b7..66f28553c6 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -666,4 +666,10 @@ lockdep_rcu_suspicious(const char *file, const int line, const char *s)
 }
 #endif
 
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+void lockdep_set_no_check_recursion(struct lockdep_map *map);
+#else
+static inline void lockdep_set_no_check_recursion(struct lockdep_map *map) {}
+#endif
+
 #endif /* __LINUX_LOCKDEP_H */
diff --git a/include/linux/lockdep_types.h b/include/linux/lockdep_types.h
index d22430840b..506e769b4a 100644
--- a/include/linux/lockdep_types.h
+++ b/include/linux/lockdep_types.h
@@ -128,7 +128,7 @@ struct lock_class {
 	u8				wait_type_inner;
 	u8				wait_type_outer;
 	u8				lock_type;
-	/* u8				hole; */
+	u8				no_check_recursion;
 
 #ifdef CONFIG_LOCK_STAT
 	unsigned long			contention_point[LOCKSTAT_POINTS];
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index cae7d5f0ad..47ffb8df11 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3023,6 +3023,9 @@ check_deadlock(struct task_struct *curr, struct held_lock *next)
 		if ((next->read == 2) && prev->read)
 			continue;
 
+		if (hlock_class(next)->no_check_recursion)
+			continue;
+
 		/*
 		 * We're holding the nest_lock, which serializes this lock's
 		 * nesting behaviour.
@@ -3084,6 +3087,10 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 		return 2;
 	}
 
+	if (hlock_class(prev) == hlock_class(next) &&
+	    hlock_class(prev)->no_check_recursion)
+		return 2;
+
 	/*
 	 * Prove that the new <prev> -> <next> dependency would not
 	 * create a circular dependency in the graph. (We do this by
@@ -6617,3 +6624,22 @@ void lockdep_rcu_suspicious(const char *file, const int line, const char *s)
 	dump_stack();
 }
 EXPORT_SYMBOL_GPL(lockdep_rcu_suspicious);
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+void lockdep_set_no_check_recursion(struct lockdep_map *lock)
+{
+	struct lock_class *class = lock->class_cache[0];
+	unsigned long flags;
+
+	raw_local_irq_save(flags);
+	lockdep_recursion_inc();
+
+	if (!class)
+		class = register_lock_class(lock, 0, 0);
+	if (class)
+		class->no_check_recursion = true;
+	lockdep_recursion_finish();
+	raw_local_irq_restore(flags);
+}
+EXPORT_SYMBOL_GPL(lockdep_set_no_check_recursion);
+#endif
-- 
2.39.1

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Kent Overstreet]

On Sat, Feb 11, 2023 at 06:06:28PM -0500, Kent Overstreet wrote:
> On 2/11/23 16:51, Linus Torvalds wrote:
> > On Sat, Feb 11, 2023 at 1:41 PM Alan Stern <stern@rowland.harvard.edu> wrote:
> > > 
> > > @@ -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);
> > 
> > So I think this is the right thing to do, but I note that while that
> > lockdep_set_novalidate_class() was "documented" to only be for
> > 'dev->mutex' by scripts/checkpatch.pl, that horrific thing is also
> > used by md/bcache/btree.c for the mca_bucket_alloc().
> > 
> > Can we *please* get rid of it there too (it was added by the initial
> > code, and never had any explicit excuse for it), possibly by using the
> > same model.
> > 
> > And then we could get rid of lockdep_set_novalidate_class() entirely.
> > That would be a good thing.
> 
> Yeah, what bcache really needs (and presumably dev->mutex as well) is just
> to disable lockdep checking for self-deadlock of that lock type, since it's
> got its own deadlock avoidance and the subclass thing isn't good enough.
> 
> I've got a patch that should do what we want, replying from my other account
> with it.

After scanning the rest of the thread: I don't think you want to create
separate lockdep classes for each bus and device type, that's defeating
how lockdep works. Maybe if it was only a small, _static_ number of new
classes, but the basic premesis of lockdep is that there are static
human understandable lock ordering rules, so lockdep figures out what
they are and checks them: if you create a bunch of dynamic classes, the
classes are going to be different for everyone in practice and won't
have any real bearing on the structure of the code - that is, given a
lockdep splat, you won't be able to do anything with it.

If static lock ordering rules aren't working (say, because the lock
ordering rules are determined by hardware relationships or what
userspace is doing), then you have to do something more sophisticated.

Wait/wound mutexes would be the next thing to look at, and DRM ended up
needing them for similar reasons as what you're running up against so I
think they bear serious consideration.

ww mutexes are the simple version of dynamic deadlock avoidance -
instead of doing full cycle detection they just compare transaction
start times, so they come at the cost of more frequent aborts. If this
is an issue for you, here's what full cycle detection looks like:

https://evilpiepirate.org/git/bcachefs.git/tree/fs/bcachefs/btree_locking.c#n53

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Kent Overstreet]

On Sun, Feb 12, 2023 at 09:32:20AM +0800, Hillf Danton wrote:
> On Sat, 11 Feb 2023 18:08:05 -0500 Kent Overstreet <kent.overstreet@linux.dev>
> > 
> > Subject: [PATCH] locking/lockdep: lockdep_set_no_check_recursion()
> > 
> > This adds a method to tell lockdep not to check lock ordering within a
> > lock class - but to still check lock ordering w.r.t. other lock types.
> 
> Given what is cut off in the rfc, better not add this to lockdep again if
> anything like checking lock_owner in reiserfs_write_lock() works for you.
> 
> Why is lockdep the dump bin for what you add?

You have zero commits to the code in question, and you're coming in here
with a total non sequitar and an insult.

Fuck off, you don't belong here.

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

On Sat, Feb 11, 2023 at 06:24:42PM -0500, Kent Overstreet wrote:
> After scanning the rest of the thread: I don't think you want to create
> separate lockdep classes for each bus and device type, that's defeating
> how lockdep works.

Not at all.  In fact, exactly the opposite: lockdep works by creating a 
class for each lock-inside-a-data-structure-type combination.  A struct 
device-bus_type/device_type combination is pretty much the same kind of 
thing.

>  Maybe if it was only a small, _static_ number of new
> classes,

The collection of bus_types and device_types _is_ static, in the sense 
that each one is a structure defined in a driver source file.  Whether 
the number is "small" depends on your tolerance for large numbers; the 
kernel has a lot of source files.  :-)

Mind you, I'm not saying that having lockdep classes for each bus_type 
or device_type is always the right thing to do.  There definitely are 
cases where it wouldn't do what we want.  But perhaps in some cases it 
would work.

> but the basic premesis of lockdep is that there are static
> human understandable lock ordering rules, so lockdep figures out what
> they are and checks them: if you create a bunch of dynamic classes, the
> classes are going to be different for everyone in practice and won't
> have any real bearing on the structure of the code

As a rule, bus_type's and device_type's aren't dynamic.  Maybe Greg KH 
once published an example of such a thing; IIRC it was more like a 
proof-of-principle rather than a serious recommendation on how to write 
drivers.  (Or else I'm misremembering and it was actually an example of 
creating dynamic sysfs attributes.)

Or maybe you're referring to what this patch does?  It does indeed 
create a bunch of dynamic classes -- one for each struct device.  The 
ordering rules derived by lockdep will be somewhat arbitrary, as you 
say.  But some of them certainly will be related to the structure of the 
source code.

For instance, there's a rule that you must not acquire a device's lock 
if you're already holding the lock of one of its descendants, and this 
is related to how device discovery works (the driver for a device is 
responsible for discovering the device's children).  But that rule alone 
isn't enough to prevent deadlocks.

>  that is, given a
> lockdep splat, you won't be able to do anything with it.

Nonsense.  Even if you don't know what the locking rules are, given a 
splat you can see what the cycle is and try to figure out which of the 
links should be invalid.  Without the splat you'd be a lot worse off.

> If static lock ordering rules aren't working (say, because the lock
> ordering rules are determined by hardware relationships or what
> userspace is doing), then you have to do something more sophisticated.
> 
> Wait/wound mutexes would be the next thing to look at, and DRM ended up
> needing them for similar reasons as what you're running up against so I
> think they bear serious consideration.
> 
> ww mutexes are the simple version of dynamic deadlock avoidance -
> instead of doing full cycle detection they just compare transaction
> start times, so they come at the cost of more frequent aborts. If this
> is an issue for you, here's what full cycle detection looks like:
> 
> https://evilpiepirate.org/git/bcachefs.git/tree/fs/bcachefs/btree_locking.c#n53

I'm not at all sure that w/w mutexes are the answer to device locking.  
Not to mention that converting over to use them would require a huge 
effort.

A typical kind of issue that seems to pop up a lot is a task trying to 
flush a work queue while holding a lock that's needed by one of the 
items on the queue.  (This isn't particularly limited to dev->mutex 
locks, of course.  It can crop up anywhere, but it seems to happen with 
some regularity in this setting.  Perhaps the fact that lockdep is 
unable to warn about these things is a contributing factor.  Can w/w 
mutexes can handle this sort of thing?  I'm not sufficiently familiar 
with them to know.)  Apparently people write this sort of code because 
they aren't aware of or don't pay attention to the context in which 
their functions run -- that is, the locks that have automatically been 
acquired by the callers.

Alan Stern

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Kent Overstreet]

On Sat, Feb 11, 2023 at 09:40:58PM -0500, Alan Stern wrote:
> On Sat, Feb 11, 2023 at 06:24:42PM -0500, Kent Overstreet wrote:
> > After scanning the rest of the thread: I don't think you want to create
> > separate lockdep classes for each bus and device type, that's defeating
> > how lockdep works.
> 
> Not at all.  In fact, exactly the opposite: lockdep works by creating a 
> class for each lock-inside-a-data-structure-type combination.  A struct 
> device-bus_type/device_type combination is pretty much the same kind of 
> thing.
> 
> >  Maybe if it was only a small, _static_ number of new
> > classes,
> 
> The collection of bus_types and device_types _is_ static, in the sense 
> that each one is a structure defined in a driver source file.  Whether 
> the number is "small" depends on your tolerance for large numbers; the 
> kernel has a lot of source files.  :-)
> 
> Mind you, I'm not saying that having lockdep classes for each bus_type 
> or device_type is always the right thing to do.  There definitely are 
> cases where it wouldn't do what we want.  But perhaps in some cases it 
> would work.
> 
> > but the basic premesis of lockdep is that there are static
> > human understandable lock ordering rules, so lockdep figures out what
> > they are and checks them: if you create a bunch of dynamic classes, the
> > classes are going to be different for everyone in practice and won't
> > have any real bearing on the structure of the code
> 
> As a rule, bus_type's and device_type's aren't dynamic.  Maybe Greg KH 
> once published an example of such a thing; IIRC it was more like a 
> proof-of-principle rather than a serious recommendation on how to write 
> drivers.  (Or else I'm misremembering and it was actually an example of 
> creating dynamic sysfs attributes.)
> 
> Or maybe you're referring to what this patch does?  It does indeed 
> create a bunch of dynamic classes -- one for each struct device.  The 
> ordering rules derived by lockdep will be somewhat arbitrary, as you 
> say.  But some of them certainly will be related to the structure of the 
> source code.

I could be :) I haven't been able to find the patch in question - have a
link?

If you're talking about making lock_class_key dynamic, I think I stand
by what I said though - OTOH, if all you're doing is lifting that to the
caller of the device object init function, so it'll still be a static
object in the driver, that would be totally fine.

I probably should've found the patch before commenting :)

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

On Sat, Feb 11, 2023 at 09:46:42PM -0500, Kent Overstreet wrote:
> On Sat, Feb 11, 2023 at 09:40:58PM -0500, Alan Stern wrote:
> > Or maybe you're referring to what this patch does?  It does indeed 
> > create a bunch of dynamic classes -- one for each struct device.  The 
> > ordering rules derived by lockdep will be somewhat arbitrary, as you 
> > say.  But some of them certainly will be related to the structure of the 
> > source code.
> 
> I could be :) I haven't been able to find the patch in question - have a
> link?

It was earlier in this email thread.  Here's a link:

https://lore.kernel.org/r/Y+gLd78vChQERZ6A@rowland.harvard.edu/

> If you're talking about making lock_class_key dynamic, I think I stand
> by what I said though - OTOH, if all you're doing is lifting that to the
> caller of the device object init function, so it'll still be a static
> object in the driver, that would be totally fine.

The patch does the first, not the second.  Feel free to object some 
more...  :-)

Alan Stern

> I probably should've found the patch before commenting :)

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Kent Overstreet]

On Sat, Feb 11, 2023 at 10:03:11PM -0500, Alan Stern wrote:
> On Sat, Feb 11, 2023 at 09:46:42PM -0500, Kent Overstreet wrote:
> > On Sat, Feb 11, 2023 at 09:40:58PM -0500, Alan Stern wrote:
> > > Or maybe you're referring to what this patch does?  It does indeed 
> > > create a bunch of dynamic classes -- one for each struct device.  The 
> > > ordering rules derived by lockdep will be somewhat arbitrary, as you 
> > > say.  But some of them certainly will be related to the structure of the 
> > > source code.
> > 
> > I could be :) I haven't been able to find the patch in question - have a
> > link?
> 
> It was earlier in this email thread.  Here's a link:
> 
> https://lore.kernel.org/r/Y+gLd78vChQERZ6A@rowland.harvard.edu/
> 
> > If you're talking about making lock_class_key dynamic, I think I stand
> > by what I said though - OTOH, if all you're doing is lifting that to the
> > caller of the device object init function, so it'll still be a static
> > object in the driver, that would be totally fine.
> 
> The patch does the first, not the second.  Feel free to object some 
> more...  :-)

So IMO the more correct way to do this would be to change
device_initialize() to __device_initialize(), have it take a
lock_class_key as a parameter, and then use __mutex_init() instead of
mutex_init().

But let's think about this more. Will there ever be situations where
lock ordering is dependent on what hardware is plugged into what, or
what hardware is plugged in first?

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

On Sat, Feb 11, 2023 at 10:10:23PM -0500, Kent Overstreet wrote:
> So IMO the more correct way to do this would be to change
> device_initialize() to __device_initialize(), have it take a
> lock_class_key as a parameter, and then use __mutex_init() instead of
> mutex_init().

Yes, maybe.  The increase in code size might outweigh the space saved.

> But let's think about this more. Will there ever be situations where
> lock ordering is dependent on what hardware is plugged into what, or
> what hardware is plugged in first?

Device lock ordering is always dependent on what hardware is plugged 
into what.  However, I'm not aware of any situations where, given two 
different kinds of hardware, either one could be plugged into the other.
Such things may exist but I can't think of any examples.

On the other hand, there are obvious cases where two pieces of the 
_same_ kind of hardware can be plugged together in either order.  USB 
hubs are a good example.

Consider the possibility that a driver might want to lock all of a 
device's children at once.  (I don't know if this ever happens, but it 
might.)  Provided it acquires the parent device's lock first, this is 
utterly safe no matter what order the children are locked in.  Try 
telling that to lockdep!  In the end, we'd probably have to enforce a 
single fixed ordering.

Alan Stern

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Kent Overstreet]

On Sun, Feb 12, 2023 at 10:23:44AM -0500, Alan Stern wrote:
> On Sat, Feb 11, 2023 at 10:10:23PM -0500, Kent Overstreet wrote:
> > So IMO the more correct way to do this would be to change
> > device_initialize() to __device_initialize(), have it take a
> > lock_class_key as a parameter, and then use __mutex_init() instead of
> > mutex_init().
> 
> Yes, maybe.  The increase in code size might outweigh the space saved.

Where would the increase in code size come from? And whatever effect
would only be when lockdep is enabled, so not a concern.

But consider that the name of a lock as registered with lockdep really
should correspond to a source code location - i.e. it should be
something you can grep for. (We should probably consider adding file and
line number to that string, since current names are not unambiguous).

Whereas in your pass, you're calling lockdep_set_class(), which
generates a class name via stringifcation - with the same name every
time.

Definitely _don't_ do that. With your patch, the generated lockdep
traces will be useless.

> > But let's think about this more. Will there ever be situations where
> > lock ordering is dependent on what hardware is plugged into what, or
> > what hardware is plugged in first?
> 
> Device lock ordering is always dependent on what hardware is plugged 
> into what.  However, I'm not aware of any situations where, given two 
> different kinds of hardware, either one could be plugged into the other.
> Such things may exist but I can't think of any examples.

Different brands of hubs?

Lots of things have hubs embedded into them these days. 15 years ago I
had an Apple keyboard with an embedded hub.

> On the other hand, there are obvious cases where two pieces of the 
> _same_ kind of hardware can be plugged together in either order.  USB 
> hubs are a good example.
> 
> Consider the possibility that a driver might want to lock all of a 
> device's children at once.  (I don't know if this ever happens, but it 
> might.)  Provided it acquires the parent device's lock first, this is 
> utterly safe no matter what order the children are locked in.  Try 
> telling that to lockdep!  In the end, we'd probably have to enforce a 
> single fixed ordering.

The way you speak of hypotheticals and possibilities makes me think that
the actual locking rules are not ironed out at all :)

The patch I posted would be an improvement over the current situation,
because it'd get you checking w.r.t. other lock types - but with that
you would still have to have your own deadlock avoidance strategy, and
you'd have to be _really_ clear on what it is and how you know that
you're getting it right - you're still opting out of checking.

I think you should really be investigating wait/wound mutexes here.

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

On Sun, Feb 12, 2023 at 02:14:02PM -0500, Kent Overstreet wrote:
> On Sun, Feb 12, 2023 at 10:23:44AM -0500, Alan Stern wrote:
> > On Sat, Feb 11, 2023 at 10:10:23PM -0500, Kent Overstreet wrote:
> > > So IMO the more correct way to do this would be to change
> > > device_initialize() to __device_initialize(), have it take a
> > > lock_class_key as a parameter, and then use __mutex_init() instead of
> > > mutex_init().
> > 
> > Yes, maybe.  The increase in code size might outweigh the space saved.
> 
> Where would the increase in code size come from?

Maybe I didn't understand your suggestion.  Did you mean that all 
callers of device_initialize() (or whatever) should be able to specify 
their own lock_class_key?  Or were you just trying to avoid the single 
static allocation of a lock_class_key in device_initialize() done as a 
side-effect of the mutex_init() call?

> And whatever effect
> would only be when lockdep is enabled, so not a concern.

Not if a new function is created (i.e., __device_initialize()).

> But consider that the name of a lock as registered with lockdep really
> should correspond to a source code location - i.e. it should be
> something you can grep for. (We should probably consider adding file and
> line number to that string, since current names are not unambiguous).
> 
> Whereas in your pass, you're calling lockdep_set_class(), which
> generates a class name via stringifcation - with the same name every
> time.
> 
> Definitely _don't_ do that. With your patch, the generated lockdep
> traces will be useless.

I'll revise the patch to use the device's name for the class.  While it 
may not be globally unique, it should be sufficiently specific.

(Device names are often set after the device is initialized.  Does 
lockdep mind if a lock_class_key's name is changed after it has been 
registered?)

> > > But let's think about this more. Will there ever be situations where
> > > lock ordering is dependent on what hardware is plugged into what, or
> > > what hardware is plugged in first?
> > 
> > Device lock ordering is always dependent on what hardware is plugged 
> > into what.  However, I'm not aware of any situations where, given two 
> > different kinds of hardware, either one could be plugged into the other.
> > Such things may exist but I can't think of any examples.
> 
> Different brands of hubs?

As far as the kernel is concerned they wouldn't be _different kinds_ of 
hardware; they would both be hubs.

> Lots of things have hubs embedded into them these days. 15 years ago I
> had an Apple keyboard with an embedded hub.

Apple keyboards get treated as two logically separate pieces of 
hardware: a hub and a keyboard.  The fact that they are packaged as a 
single unit is irrelevant.

> > On the other hand, there are obvious cases where two pieces of the 
> > _same_ kind of hardware can be plugged together in either order.  USB 
> > hubs are a good example.
> > 
> > Consider the possibility that a driver might want to lock all of a 
> > device's children at once.  (I don't know if this ever happens, but it 
> > might.)  Provided it acquires the parent device's lock first, this is 
> > utterly safe no matter what order the children are locked in.  Try 
> > telling that to lockdep!  In the end, we'd probably have to enforce a 
> > single fixed ordering.
> 
> The way you speak of hypotheticals and possibilities makes me think that
> the actual locking rules are not ironed out at all :)

You're right.  There are no explicitly documented rules for device 
locking as far as I'm aware.  Each subsystem handles its own locking 
independently (but self-consistently, we hope).  That's one of the 
reasons that creating lockdep rules for devices is so difficult.

The business about not locking a parent if you already own the child's 
lock is perhaps the only universal -- and I don't know that it's written 
down anywhere.

> The patch I posted would be an improvement over the current situation,
> because it'd get you checking w.r.t. other lock types - but with that
> you would still have to have your own deadlock avoidance strategy, and
> you'd have to be _really_ clear on what it is and how you know that
> you're getting it right - you're still opting out of checking.

Same with the patch I posted, except that it opts back into checking.

> I think you should really be investigating wait/wound mutexes here.

At this stage, converting would be most impractical.  And I don't think 
it's really needed.

Alan Stern

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Kent Overstreet]

On Sun, Feb 12, 2023 at 03:19:16PM -0500, Alan Stern wrote:
> Maybe I didn't understand your suggestion.  Did you mean that all 
> callers of device_initialize() (or whatever) should be able to specify 
> their own lock_class_key?  Or were you just trying to avoid the single 
> static allocation of a lock_class_key in device_initialize() done as a 
> side-effect of the mutex_init() call?
> 
> > And whatever effect
> > would only be when lockdep is enabled, so not a concern.
> 
> Not if a new function is created (i.e., __device_initialize()).

Follow the same pattern as mutex_init() - have a look over that code.

> > But consider that the name of a lock as registered with lockdep really
> > should correspond to a source code location - i.e. it should be
> > something you can grep for. (We should probably consider adding file and
> > line number to that string, since current names are not unambiguous).
> > 
> > Whereas in your pass, you're calling lockdep_set_class(), which
> > generates a class name via stringifcation - with the same name every
> > time.
> > 
> > Definitely _don't_ do that. With your patch, the generated lockdep
> > traces will be useless.
> 
> I'll revise the patch to use the device's name for the class.  While it 
> may not be globally unique, it should be sufficiently specific.
> 
> (Device names are often set after the device is initialized.  Does 
> lockdep mind if a lock_class_key's name is changed after it has been 
> registered?)

The device name should _not_ be something dynamic, it should be
something easily tied back to a source code location - i.e. related to
the driver name, not the device name.

That's how people read and use lockdep reports!

Do it exactly the same way mutex_init() does it, just lift it up a level
to a wrapper around device_initialize() - stringify the pointer to the
mutex (embedded in struct device, embedded in what-have-you driver code)
and use that.

> You're right.  There are no explicitly documented rules for device 
> locking as far as I'm aware.  Each subsystem handles its own locking 
> independently (but self-consistently, we hope).  That's one of the 
> reasons that creating lockdep rules for devices is so difficult.
> 
> The business about not locking a parent if you already own the child's 
> lock is perhaps the only universal -- and I don't know that it's written 
> down anywhere.

Yeah that's sketchy; if the rules are too complicated to be written
down, they're too complicated.

One thing that could be contemplated is adding support for user-defined
comparison functions to lockdep, to define a lock ordering within a
class when subclass isn't sufficient.

That would work for bcache - for bcache the lock ordering is parent
nodes before children, and if multiple nodes are locked at the same
level they have to be locked in natural key order.

But, this would add a lot of complexity to lockdep, and this is the sort
of situation where if you have a bug in the comparison function (i.e. it
doesn't define a total ordering) it'll break things in terribly fun
ways.

> > The patch I posted would be an improvement over the current situation,
> > because it'd get you checking w.r.t. other lock types - but with that
> > you would still have to have your own deadlock avoidance strategy, and
> > you'd have to be _really_ clear on what it is and how you know that
> > you're getting it right - you're still opting out of checking.
> 
> Same with the patch I posted, except that it opts back into checking.
> 
> > I think you should really be investigating wait/wound mutexes here.
> 
> At this stage, converting would be most impractical.  And I don't think 
> it's really needed.

They do make you deal with lock restarts; unwinding typical stateful
kernel code is not necessarily super practical :)

Anyways, it sounds like the lockdep-class-per-driver approach will get
you more information, that's certainly a reasonable approach for now.

Cheers,
-Kent

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

On Sun, Feb 12, 2023 at 03:51:05PM -0500, Kent Overstreet wrote:
> On Sun, Feb 12, 2023 at 03:19:16PM -0500, Alan Stern wrote:
> > I'll revise the patch to use the device's name for the class.  While it 
> > may not be globally unique, it should be sufficiently specific.
> > 
> > (Device names are often set after the device is initialized.  Does 
> > lockdep mind if a lock_class_key's name is changed after it has been 
> > registered?)
> 
> The device name should _not_ be something dynamic, it should be
> something easily tied back to a source code location - i.e. related to
> the driver name, not the device name.
> 
> That's how people read and use lockdep reports!
> 
> Do it exactly the same way mutex_init() does it, just lift it up a level
> to a wrapper around device_initialize() - stringify the pointer to the
> mutex (embedded in struct device, embedded in what-have-you driver code)
> and use that.

I really don't think that's a good idea here.  When you've got a bus 
containing multiple devices, typically all those device structures are 
created by the same line of code.  So knowing the source code location 
won't tell you _which_ device structure is involved in the locking 
cycle or what driver it's using.  By contrast, knowing the device name 
would.

Furthermore, to the extent that the device's name identifies what kind 
of device it is, the name would tell you what where the structure was 
created and which driver it is using.

For example, knowing that a struct device was initialized in line 2104 
of drivers/usb/core/message.c tells you only that the device is a USB 
interface.  It doesn't tell you which USB interface.  But knowing that 
the device's name is 1-7:1.1 not only tells me that the device is a USB 
interface, it also allows me to do:

$ ls -l /sys/bus/usb/devices/1-7:1.1/driver
lrwxrwxrwx. 1 root root 0 Feb 12 19:56 /sys/bus/usb/devices/1-7:1.1/driver -> ../../../../../../bus/usb/drivers/usbhid/

telling me that the device is some sort of HID device.  Probably my 
laptop's touchpad (which could easily be verified).  Even without direct 
interaction with the system, searching through the kernel log would give 
me this information.

> > At this stage, converting would be most impractical.  And I don't think 
> > it's really needed.
> 
> They do make you deal with lock restarts; unwinding typical stateful
> kernel code is not necessarily super practical :)
> 
> Anyways, it sounds like the lockdep-class-per-driver approach will get
> you more information, that's certainly a reasonable approach for now.

Thanks for the review and suggestions.

Alan Stern

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Kent Overstreet]

On Sun, Feb 12, 2023 at 08:23:34PM -0500, Alan Stern wrote:
> I really don't think that's a good idea here.  When you've got a bus 
> containing multiple devices, typically all those device structures are 
> created by the same line of code.  So knowing the source code location 
> won't tell you _which_ device structure is involved in the locking 
> cycle or what driver it's using.

Yeah, I was thinking about this more and realized it'd be insufficient.

> By contrast, knowing the device name 
> would.
> 
> Furthermore, to the extent that the device's name identifies what kind 
> of device it is, the name would tell you what where the structure was 
> created and which driver it is using.

OTOH, with the device name, it seems like you'll additionally need the
full device topology to be able to do anything with lockdep splats, no?

What if we just added a way to set a comparison function for a lockdep
class? I'm looking at the lockdep code now, and I think I could do that
for you.

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Peter Zijlstra]

On Sun, Feb 12, 2023 at 10:23:44AM -0500, Alan Stern wrote:
> Provided it acquires the parent device's lock first, this is 
> utterly safe no matter what order the children are locked in.  Try 
> telling that to lockdep! 

mutex_lock_next_lock(child->lock, parent->lock) is there to express this
exact pattern, it allows taking multiple child->lock class locks (in any
order) provided parent->lock is held.

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Peter Zijlstra]

On Sun, Feb 12, 2023 at 03:19:16PM -0500, Alan Stern wrote:

> (Device names are often set after the device is initialized.  Does 
> lockdep mind if a lock_class_key's name is changed after it has been 
> registered?)

It does, althought I don't at the moment recall how hard it would be to
change that.

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Peter Zijlstra]

On Sun, Feb 12, 2023 at 03:51:05PM -0500, Kent Overstreet wrote:
> But, this would add a lot of complexity to lockdep, and this is the sort
> of situation where if you have a bug in the comparison function (i.e. it
> doesn't define a total ordering) it'll break things in terribly fun
> ways.

FWIW, it is possible to annotate an actual deadlock away with many of
the lockdep annotations -- care is always needed with this stuff.

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Peter Zijlstra]

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.

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.

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

On Sun, Feb 12, 2023 at 09:21:14PM -0500, Kent Overstreet wrote:
> On Sun, Feb 12, 2023 at 08:23:34PM -0500, Alan Stern wrote:
> > I really don't think that's a good idea here.  When you've got a bus 
> > containing multiple devices, typically all those device structures are 
> > created by the same line of code.  So knowing the source code location 
> > won't tell you _which_ device structure is involved in the locking 
> > cycle or what driver it's using.
> 
> Yeah, I was thinking about this more and realized it'd be insufficient.
> 
> > By contrast, knowing the device name 
> > would.
> > 
> > Furthermore, to the extent that the device's name identifies what kind 
> > of device it is, the name would tell you what where the structure was 
> > created and which driver it is using.
> 
> OTOH, with the device name, it seems like you'll additionally need the
> full device topology to be able to do anything with lockdep splats, no?

Not necessarily.  Knowing the name already tells you something about 
where the device fits into the full tree.  And if necessary, you can 
probably glean the necessary information from the kernel log.

Besides, you often don't need the full device topology.  For instance, 
if the problem is that a driver is flushing a work queue while holding a 
lock needed by an item on the queue, mostly you just need to know what 
driver and where the flush occurs -- and that information is already 
provided by lockdep.

> What if we just added a way to set a comparison function for a lockdep
> class? I'm looking at the lockdep code now, and I think I could do that
> for you.

I don't know what a lockdep class comparison function does (or would 
do).  Nor how having one would help.

Alan Stern

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

On Mon, Feb 13, 2023 at 10:24:13AM +0100, Peter Zijlstra wrote:
> On Sun, Feb 12, 2023 at 10:23:44AM -0500, Alan Stern wrote:
> > Provided it acquires the parent device's lock first, this is 
> > utterly safe no matter what order the children are locked in.  Try 
> > telling that to lockdep! 
> 
> mutex_lock_next_lock(child->lock, parent->lock) is there to express this
> exact pattern, it allows taking multiple child->lock class locks (in any
> order) provided parent->lock is held.

Ah, this is news to me.  Is this sort of thing documented somewhere?

Alan Stern

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

On Mon, Feb 13, 2023 at 10:27:18AM +0100, Peter Zijlstra wrote:
> On Sun, Feb 12, 2023 at 03:19:16PM -0500, Alan Stern wrote:
> 
> > (Device names are often set after the device is initialized.  Does 
> > lockdep mind if a lock_class_key's name is changed after it has been 
> > registered?)
> 
> It does, althought I don't at the moment recall how hard it would be to
> change that.

If the names are only used for printing purposes, or other similarly 
innocuous things, it ought to be enough to set the name with 
smp_store_release() and read the name with smp_load_acquire().

Alan Stern

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

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

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Peter Zijlstra]

On Mon, Feb 13, 2023 at 10:25:59AM -0500, Alan Stern wrote:
> On Mon, Feb 13, 2023 at 10:24:13AM +0100, Peter Zijlstra wrote:
> > On Sun, Feb 12, 2023 at 10:23:44AM -0500, Alan Stern wrote:
> > > Provided it acquires the parent device's lock first, this is 
> > > utterly safe no matter what order the children are locked in.  Try 
> > > telling that to lockdep! 
> > 
> > mutex_lock_next_lock(child->lock, parent->lock) is there to express this
> > exact pattern, it allows taking multiple child->lock class locks (in any
> > order) provided parent->lock is held.
> 
> Ah, this is news to me.  Is this sort of thing documented somewhere?

Probably not :/

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Peter Zijlstra]

On Mon, Feb 13, 2023 at 10:28:08AM -0500, Alan Stern wrote:
> On Mon, Feb 13, 2023 at 10:27:18AM +0100, Peter Zijlstra wrote:
> > On Sun, Feb 12, 2023 at 03:19:16PM -0500, Alan Stern wrote:
> > 
> > > (Device names are often set after the device is initialized.  Does 
> > > lockdep mind if a lock_class_key's name is changed after it has been 
> > > registered?)
> > 
> > It does, althought I don't at the moment recall how hard it would be to
> > change that.
> 
> If the names are only used for printing purposes, or other similarly 
> innocuous things, it ought to be enough to set the name with 
> smp_store_release() and read the name with smp_load_acquire().

The name is copied from the key to the 'class' upon registration of the
first lock that uses a particular key. Then later, when looking up the
class for subsequent usages of the same key, the string is checked, and
WARNs if they somehow not match.

Granted, this is a silly sanity check that's easily disabled. But from a
cursory look that seems to be just about it.

The only 'problem' is that it's (typically) class name that's printed,
not the key name, so if you change the key name, without also changing
the class name, reports get really confusing.

Still, that all ought to be fixable.. just a matter of typing or so :-)

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Greg Kroah-Hartman]

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

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

On Mon, Feb 13, 2023 at 06:51:57PM +0100, Greg Kroah-Hartman wrote:
> 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?

A large part of the reason those syzbot reports didn't make any sense 
was because they didn't include any lockdep information.  Making lockdep 
aware of device locking would make those reports a lot easier to 
understand and would help with fixing the bugs.  And it might even help 
with catching similar problems before they get merged into the kernel.

Will it be worthwhile in the end?  I have no idea.

Alan Stern

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Kent Overstreet]

On Mon, Feb 13, 2023 at 10:24:13AM +0100, Peter Zijlstra wrote:
> On Sun, Feb 12, 2023 at 10:23:44AM -0500, Alan Stern wrote:
> > Provided it acquires the parent device's lock first, this is 
> > utterly safe no matter what order the children are locked in.  Try 
> > telling that to lockdep! 
> 
> mutex_lock_next_lock(child->lock, parent->lock) is there to express this
> exact pattern, it allows taking multiple child->lock class locks (in any
> order) provided parent->lock is held.

Perhaps I'm stupid, but I've never understood how subclasses - or this -
are supposed to work.

Locks don't get a fixed subclass, so what's to prevent some code from
going

/* thread 1: */
mutex_lock(&a->lock);
mutex_lock_nested(&b->lock, 1);

/* thread 2: */
mutex_lock(&b->lock);
mutex_lock_nested(&a->lock, 1);

I don't see how they can be used to check that we're obeying a lock
ordering?

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Boqun Feng]

On Mon, Feb 13, 2023 at 05:29:49PM +0100, Peter Zijlstra wrote:
> On Mon, Feb 13, 2023 at 10:25:59AM -0500, Alan Stern wrote:
> > On Mon, Feb 13, 2023 at 10:24:13AM +0100, Peter Zijlstra wrote:
> > > On Sun, Feb 12, 2023 at 10:23:44AM -0500, Alan Stern wrote:
> > > > Provided it acquires the parent device's lock first, this is 
> > > > utterly safe no matter what order the children are locked in.  Try 
> > > > telling that to lockdep! 
> > > 
> > > mutex_lock_next_lock(child->lock, parent->lock) is there to express this
> > > exact pattern, it allows taking multiple child->lock class locks (in any
> > > order) provided parent->lock is held.
> > 
> > Ah, this is news to me.  Is this sort of thing documented somewhere?

Basically if you have two lock instances A and B with the same class,
and you know that locking ordering is always A -> B, then you can do

	mutex_lock(A);
	mutex_lock_nest_lock(B, A); // lock B.

to tell the lockdep this is not deadlock, plus lockdep will treat the
acquisition of A and the precondition of acquisition B, so the following
is not a deadlock as well:

T1:
	mutex_lock(A);
	mutex_lock(C);
	mutex_lock_nest_lock(B, A);

T2:
	mutex_lock(A);
	mutex_lock_nest_lock(B, A);
	mutex_lock(C);

Regards,
Boqun

> 
> Probably not :/

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Boqun Feng]

On Mon, Feb 13, 2023 at 05:51:11PM -0800, Boqun Feng wrote:
> On Mon, Feb 13, 2023 at 05:29:49PM +0100, Peter Zijlstra wrote:
> > On Mon, Feb 13, 2023 at 10:25:59AM -0500, Alan Stern wrote:
> > > On Mon, Feb 13, 2023 at 10:24:13AM +0100, Peter Zijlstra wrote:
> > > > On Sun, Feb 12, 2023 at 10:23:44AM -0500, Alan Stern wrote:
> > > > > Provided it acquires the parent device's lock first, this is 
> > > > > utterly safe no matter what order the children are locked in.  Try 
> > > > > telling that to lockdep! 
> > > > 
> > > > mutex_lock_next_lock(child->lock, parent->lock) is there to express this
> > > > exact pattern, it allows taking multiple child->lock class locks (in any
> > > > order) provided parent->lock is held.
> > > 
> > > Ah, this is news to me.  Is this sort of thing documented somewhere?
> 
> Basically if you have two lock instances A and B with the same class,
> and you know that locking ordering is always A -> B, then you can do
> 
> 	mutex_lock(A);
> 	mutex_lock_nest_lock(B, A); // lock B.
> 
> to tell the lockdep this is not deadlock, plus lockdep will treat the
> acquisition of A and the precondition of acquisition B, so the following

^^^
acquisition of A *as* the precondition of acquisition B

Regards,
Boqun

> is not a deadlock as well:
> 
> T1:
> 	mutex_lock(A);
> 	mutex_lock(C);
> 	mutex_lock_nest_lock(B, A);
> 
> T2:
> 	mutex_lock(A);
> 	mutex_lock_nest_lock(B, A);
> 	mutex_lock(C);
> 
> Regards,
> Boqun
> 
> > 
> > Probably not :/
> 

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

On Mon, Feb 13, 2023 at 05:51:11PM -0800, Boqun Feng wrote:
> Basically if you have two lock instances A and B with the same class,
> and you know that locking ordering is always A -> B, then you can do
> 
> 	mutex_lock(A);
> 	mutex_lock_nest_lock(B, A); // lock B.
> 
> to tell the lockdep this is not deadlock, plus lockdep will treat the
> acquisition of A and the precondition of acquisition B, so the following
> is not a deadlock as well:
> 
> T1:
> 	mutex_lock(A);
> 	mutex_lock(C);
> 	mutex_lock_nest_lock(B, A);
> 
> T2:
> 	mutex_lock(A);
> 	mutex_lock_nest_lock(B, A);
> 	mutex_lock(C);

Why isn't this treated as a deadlock?  It sure looks like a deadlock to 
me.  Is this an example where lockdep just doesn't get the right answer?

Alan Stern

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Boqun Feng]

On Mon, Feb 13, 2023 at 09:03:14PM -0500, Alan Stern wrote:
> On Mon, Feb 13, 2023 at 05:51:11PM -0800, Boqun Feng wrote:
> > Basically if you have two lock instances A and B with the same class,
> > and you know that locking ordering is always A -> B, then you can do
> > 
> > 	mutex_lock(A);
> > 	mutex_lock_nest_lock(B, A); // lock B.
> > 
> > to tell the lockdep this is not deadlock, plus lockdep will treat the
> > acquisition of A and the precondition of acquisition B, so the following
> > is not a deadlock as well:
> > 
> > T1:
> > 	mutex_lock(A);
> > 	mutex_lock(C);
> > 	mutex_lock_nest_lock(B, A);
> > 
> > T2:
> > 	mutex_lock(A);
> > 	mutex_lock_nest_lock(B, A);
> > 	mutex_lock(C);
> 
> Why isn't this treated as a deadlock?  It sure looks like a deadlock to 
> me.  Is this an example where lockdep just doesn't get the right answer?
> 

Because A serializes B and C, so that particular piece of code doesn't
cause deadlock. Note that you can still use you normal mutex_lock() for
B, so if there is more code:

T3:
	mutex_lock(C);
	mutex_lock(B);

lockdep will report deadlock.

Regards,
Boqun

> Alan Stern

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Boqun Feng]

On Tue, Feb 14, 2023 at 01:27:33PM +0800, Hillf Danton wrote:
> On Mon, 13 Feb 2023 18:09:16 -0800 Boqun Feng <boqun.feng@gmail.com>
> > On Mon, Feb 13, 2023 at 09:03:14PM -0500, Alan Stern wrote:
> > > On Mon, Feb 13, 2023 at 05:51:11PM -0800, Boqun Feng wrote:
> > > > Basically if you have two lock instances A and B with the same class,
> > > > and you know that locking ordering is always A -> B, then you can do
> > > > 
> > > > 	mutex_lock(A);
> > > > 	mutex_lock_nest_lock(B, A); // lock B.
> > > > 
> > > > to tell the lockdep this is not deadlock, plus lockdep will treat the
> > > > acquisition of A and the precondition of acquisition B, so the following
> > > > is not a deadlock as well:
> > > > 
> > > > T1:
> > > > 	mutex_lock(A);
> > > > 	mutex_lock(C);
> > > > 	mutex_lock_nest_lock(B, A);
> > > > 
> > > > T2:
> > > > 	mutex_lock(A);
> > > > 	mutex_lock_nest_lock(B, A);
> > > > 	mutex_lock(C);
> > > 
> > > Why isn't this treated as a deadlock?  It sure looks like a deadlock to 
> > > me.  Is this an example where lockdep just doesn't get the right answer?
> 
> Syzbot reported deadlock[1] with A ignored.
> 
> [1] https://lore.kernel.org/linux-mm/20230130073136.59-1-hdanton@sina.com/
> 

Right, I think that's a false positive, however it's not related to
mutex_lock_nest_lock(). Anyway mutex_lock_nest_lock() cannot help that
case since these are three different lock class.

Actually, reading the code again, I think I made a mistake, for
mutex_lock_nest_lock(), the following *is* a deadlock to lockdep:

T1:
	mutex_lock(A);
	mutex_lock(C);
	mutex_lock_nest_lock(B, A);

T2:
	mutex_lock(A);
	mutex_lock_nest_lock(B, A);
	mutex_lock(C);

and this *is not* a deadlock to lockdep:

T1:
	mutex_lock(A);
	mutex_lock_nest_lock(C, A);
	mutex_lock_nest_lock(B, A);

T2:
	mutex_lock(A);
	mutex_lock_nest_lock(B, A);
	mutex_lock_nest_lock(C, A);

The current semantics of _nest_lock() is tricky, it only provides the
"nest" effect if it is the next lock acquired after the "parent" lock.
Maybe we can change and make it clear a little bit to make it more
useful.

Ah, actually someone found it 7 years ago:

https://lore.kernel.org/lkml/20150810095247.GA4606@fixme-laptop.cn.ibm.com/

;-)

Regards,
Boqun

> > Because A serializes B and C, so that particular piece of code doesn't
> > cause deadlock. Note that you can still use you normal mutex_lock() for
> > B, so if there is more code:
> > 
> > T3:
> > 	mutex_lock(C);
> > 	mutex_lock(B);
> > 
> > lockdep will report deadlock.
> > 
> > Regards,
> > Boqun
> > 
> > > Alan Stern

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Peter Zijlstra]

On Mon, Feb 13, 2023 at 05:51:11PM -0800, Boqun Feng wrote:
> On Mon, Feb 13, 2023 at 05:29:49PM +0100, Peter Zijlstra wrote:
> > On Mon, Feb 13, 2023 at 10:25:59AM -0500, Alan Stern wrote:
> > > On Mon, Feb 13, 2023 at 10:24:13AM +0100, Peter Zijlstra wrote:
> > > > On Sun, Feb 12, 2023 at 10:23:44AM -0500, Alan Stern wrote:
> > > > > Provided it acquires the parent device's lock first, this is 
> > > > > utterly safe no matter what order the children are locked in.  Try 
> > > > > telling that to lockdep! 
> > > > 
> > > > mutex_lock_next_lock(child->lock, parent->lock) is there to express this
> > > > exact pattern, it allows taking multiple child->lock class locks (in any
> > > > order) provided parent->lock is held.
> > > 
> > > Ah, this is news to me.  Is this sort of thing documented somewhere?
> 
> Basically if you have two lock instances A and B with the same class,
> and you know that locking ordering is always A -> B, then you can do
> 
> 	mutex_lock(A);
> 	mutex_lock_nest_lock(B, A); // lock B.
> 

No, this isn't quite right, You need at least 3 locks and 2 classes.

P, C1, C2

Then:

	mutex_lock(P)
	mutex_lock_next_lock(C1, P)
	mutex_lock_next_lock(C2, P)

And it will accept any order of Cn -- since it assumes that any
multi-lock of Cn will always hold P, therefore the ordering fully given
by P.

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Peter Zijlstra]

On Mon, Feb 13, 2023 at 01:46:11PM -0500, Kent Overstreet wrote:
> On Mon, Feb 13, 2023 at 10:24:13AM +0100, Peter Zijlstra wrote:
> > On Sun, Feb 12, 2023 at 10:23:44AM -0500, Alan Stern wrote:
> > > Provided it acquires the parent device's lock first, this is 
> > > utterly safe no matter what order the children are locked in.  Try 
> > > telling that to lockdep! 
> > 
> > mutex_lock_next_lock(child->lock, parent->lock) is there to express this
> > exact pattern, it allows taking multiple child->lock class locks (in any
> > order) provided parent->lock is held.
> 
> Perhaps I'm stupid, but I've never understood how subclasses - or this -
> are supposed to work.
> 
> Locks don't get a fixed subclass, so what's to prevent some code from
> going

So there's two annotations here, the nest_lock thing and subclasses,
they're distinct things.

Every class gets a fixed 8 subclasses (0-7) given by the unique byte
addresses inside the actual key object.

Subclasses will let you create nesting order of the same class that are
acceptable. Typically lock/1 nests inside lock/0, but that's not
hard-coded, simply convention.

The way it is used is given an external lock order, say the CPU number
for the runqueue locks, you do things like:

void double_rq_lock(struct rq *rq1, struct rq *r2)
{
	lockdep_assert_irqs_disabled();

	if (rq_order_less(r2, rq1))
		swap(rq1, rq2);

	raw_spin_rq_lock(rq1);
	if (__rq_lockp(rq1) != __rq_lock(rq2))
		raw_spin_rq_lock_nested(rq2, SINGLE_DEPTH_NESTING);

	...
}

(which is more complicated than it needs to be due to the whole
core-scheduling mess, but should still be readable I suppose).

Basically we make sure rq1 and rq2 are in the correct order and acquire
them with subclass 0 (the default) and subcless 1 (SINGLE_DEPTH_NESTING)
resp. dictating the subclass order.

This is lock order per decree, if you get the order function wrong
lockdep will not see the inversion but you *will* deadlock.


Then there's that nesting lock, that requires two classes and at least 3
locks to make sense:

  P, C1, C2

Where we posit that any multi-lock of Cn is fully serialized by P and it
is used like:

	mutex_lock(P);
	mutex_lock_nest_lock(C1, P);
	mutex_lock_nest_lock(C2, P);

Where any order of Cn is acceptable, because fully ordered by P.

If you were to combine this with subclass on Cn to allow multi-lock
instances not order by P, you get to keep the pieces :-)

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Boqun Feng]

On Tue, Feb 14, 2023 at 11:48:07AM +0100, Peter Zijlstra wrote:
> On Mon, Feb 13, 2023 at 05:51:11PM -0800, Boqun Feng wrote:
> > On Mon, Feb 13, 2023 at 05:29:49PM +0100, Peter Zijlstra wrote:
> > > On Mon, Feb 13, 2023 at 10:25:59AM -0500, Alan Stern wrote:
> > > > On Mon, Feb 13, 2023 at 10:24:13AM +0100, Peter Zijlstra wrote:
> > > > > On Sun, Feb 12, 2023 at 10:23:44AM -0500, Alan Stern wrote:
> > > > > > Provided it acquires the parent device's lock first, this is 
> > > > > > utterly safe no matter what order the children are locked in.  Try 
> > > > > > telling that to lockdep! 
> > > > > 
> > > > > mutex_lock_next_lock(child->lock, parent->lock) is there to express this
> > > > > exact pattern, it allows taking multiple child->lock class locks (in any
> > > > > order) provided parent->lock is held.
> > > > 
> > > > Ah, this is news to me.  Is this sort of thing documented somewhere?
> > 
> > Basically if you have two lock instances A and B with the same class,
> > and you know that locking ordering is always A -> B, then you can do
> > 
> > 	mutex_lock(A);
> > 	mutex_lock_nest_lock(B, A); // lock B.
> > 
> 
> No, this isn't quite right, You need at least 3 locks and 2 classes.
> 
> P, C1, C2
> 
> Then:
> 
> 	mutex_lock(P)
> 	mutex_lock_next_lock(C1, P)
> 	mutex_lock_next_lock(C2, P)
> 
> And it will accept any order of Cn -- since it assumes that any
> multi-lock of Cn will always hold P, therefore the ordering fully given
> by P.

Ah, right, I was missing the fact that it works with 2 classes...

But I think with only one class, the nest_lock() still works, right?
In other words, if P and Cn are the same lock class in your example.

Also seems I gave a wrong answer to Alan, just to clarify, the following
is not a deadlock to lockdep:

T1:
	mutex_lock(P)
	mutex_lock_next_lock(C1, P)
	mutex_lock_next_lock(C2, P)
	mutex_lock(B)

T2:
	mutex_lock(P)
	mutex_lock(B)
	mutex_lock_next_lock(C1, P)
	mutex_lock_next_lock(C2, P)

Because of any pair of

	mutex_lock(L);
	... // other locks maybe
	mutex_lock_nest_lock(M, L);

lockdep will not add M into the dependency graph, since it's nested and
should be serialized by L.

Regards,
Boqun

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Alan Stern]

On Tue, Feb 14, 2023 at 12:05:27PM +0100, Peter Zijlstra wrote:
> Every class gets a fixed 8 subclasses (0-7) given by the unique byte
> addresses inside the actual key object.
> 
> Subclasses will let you create nesting order of the same class that are
> acceptable. Typically lock/1 nests inside lock/0, but that's not
> hard-coded, simply convention.

Can you explain in more detail how this works in the lockdep checking 
algorithm?  (For simplicity, let's leave out issues of interrupt status 
and other environmental things.)

I've been assuming that lockdep builds up a set of links between the 
classes -- namely, a link is created from A to B whenever a thread holds 
a lock of class A while acquiring a lock of class B.  The checking part 
would then amount to just making sure that these links don't form any 
cycles.

So then how do subclasses fit into the picture?  Is it just that now the 
links are between subclasses rather than classes, so it's not 
automatically wrong to hold a lock while acquiring another lock of the 
same class as long as the two acquisitions are in different subclasses?  
But you can still provoke a violation if there's a cycle among the 
subclasses?

> Then there's that nesting lock, that requires two classes and at least 3
> locks to make sense:
> 
>   P, C1, C2
> 
> Where we posit that any multi-lock of Cn is fully serialized by P

Assuming the speculations above are correct, how does the algorithm take 
lockdep nesting into account?  Does it simply avoid creating a link from 
subclass C to itself if both C1 and C2 were acquired while holding a 
lock of the parent subclass and both acquisitions were annotated with 
mutex_lock_next_lock()?  Or is there more to it than that?  (And should 
I have written class rather than subclass?)

And Kent, how does your proposed lockdep_set_no_check_recursion() work?  
Does it just prevent lockdep from creating a link between any two 
subclasses of the specified class?  Does it do anything more?

Alan

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Kent Overstreet]

On Tue, Feb 14, 2023 at 12:05:27PM +0100, Peter Zijlstra wrote:
> This is lock order per decree, if you get the order function wrong
> lockdep will not see the inversion but you *will* deadlock.

Yeah, that's what I mean. Given that a subclass isn't a fixed thing you
assign to a lock, just something you magic up as needed - I just don't
see what this gets us?

Why not just tell lockdep what the order function is directly?

(I know, I've been saying I'd write a patch for this, I'll get around to
it, I swear :)

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Peter Zijlstra]

On Tue, Feb 14, 2023 at 03:05:42PM -0500, Alan Stern wrote:
> On Tue, Feb 14, 2023 at 12:05:27PM +0100, Peter Zijlstra wrote:
> > Every class gets a fixed 8 subclasses (0-7) given by the unique byte
> > addresses inside the actual key object.
> > 
> > Subclasses will let you create nesting order of the same class that are
> > acceptable. Typically lock/1 nests inside lock/0, but that's not
> > hard-coded, simply convention.
> 
> Can you explain in more detail how this works in the lockdep checking 
> algorithm?  (For simplicity, let's leave out issues of interrupt status 
> and other environmental things.)
> 
> I've been assuming that lockdep builds up a set of links between the 
> classes -- namely, a link is created from A to B whenever a thread holds 
> a lock of class A while acquiring a lock of class B.  The checking part 
> would then amount to just making sure that these links don't form any 
> cycles.
> 
> So then how do subclasses fit into the picture?  Is it just that now the 
> links are between subclasses rather than classes, so it's not 
> automatically wrong to hold a lock while acquiring another lock of the 
> same class as long as the two acquisitions are in different subclasses?  
> But you can still provoke a violation if there's a cycle among the 
> subclasses?

For all intents and purposes the subclasses are fully distinct classes
from the validation pov.

	mutex_lock(L);
	mutex_lock_nested(L, 0);

are equivalent (ignoring lockdep_set_subclass()), and

	mutex_lock_nested(L, 1);

is a distinct class, validation wise. So if you write:

	mutex_lock(L1);
	mutex_lock_nested(L2, 1);

you explicitly create a lock order between the distinct validation
classes: L/0,  L/1

> > Then there's that nesting lock, that requires two classes and at least 3
> > locks to make sense:
> > 
> >   P, C1, C2
> > 
> > Where we posit that any multi-lock of Cn is fully serialized by P
> 
> Assuming the speculations above are correct, how does the algorithm take 
> lockdep nesting into account?  Does it simply avoid creating a link from 
> subclass C to itself if both C1 and C2 were acquired while holding a 
> lock of the parent subclass and both acquisitions were annotated with 
> mutex_lock_next_lock()?

Basically this; it will explicitly ignore the nesting.

Given:

	mutex_lock(P);
	mutex_lock_nest_lock(C1, P);
	mutex_lock_nest_lock(C2, P);

mutex_lock_nest_lock() basically does:

 - validate that the instance of P is actually held.
   (as such, mutex_lock_nest_lock(C1, P1); mutex_lock_nest_lock(C2, P2);
   will cause objections).

 - either:

   * establish P->C in the held-lock stack
     and update the graph if so required

   * find the existing C in the held-lock stack
     and instead of complaining about class recursion, increment a
     refcount, and leave the held-stack and thus the graph unmodified.

subsequent mutex_unlock() will decrement the refcount and only when 0
'pop' the actual entry from the held stack.

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Peter Zijlstra]

On Tue, Feb 14, 2023 at 08:22:28AM -0800, Boqun Feng wrote:

> Ah, right, I was missing the fact that it works with 2 classes...
> 
> But I think with only one class, the nest_lock() still works, right?
> In other words, if P and Cn are the same lock class in your example.

I don't think so, but I don't think I've carefully considered that case.

> Also seems I gave a wrong answer to Alan, just to clarify, the following
> is not a deadlock to lockdep:
> 
> T1:
> 	mutex_lock(P)
> 	mutex_lock_next_lock(C1, P)
> 	mutex_lock_next_lock(C2, P)
> 	mutex_lock(B)
> 
> T2:
> 	mutex_lock(P)
> 	mutex_lock(B)
> 	mutex_lock_next_lock(C1, P)
> 	mutex_lock_next_lock(C2, P)
> 

This should in fact complain about a CB-BC deadlock, (but I've not
tested it, just going on memories of how I implemented it).

> Because of any pair of
> 
> 	mutex_lock(L);
> 	... // other locks maybe
> 	mutex_lock_nest_lock(M, L);
> 
> lockdep will not add M into the dependency graph, since it's nested and
> should be serialized by L.

We do enter M into the dependency graph, but instead ignore M-M
recursion. Specifically so that we might catch the above deadlock vs B.

Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Boqun Feng]

On Wed, Feb 15, 2023 at 11:45:03AM +0100, Peter Zijlstra wrote:
> On Tue, Feb 14, 2023 at 08:22:28AM -0800, Boqun Feng wrote:
> 
> > Ah, right, I was missing the fact that it works with 2 classes...
> > 
> > But I think with only one class, the nest_lock() still works, right?
> > In other words, if P and Cn are the same lock class in your example.

After playing with some self test cases, I found I was wrong again ;-(

> 
> I don't think so, but I don't think I've carefully considered that case.
> 

You are right, the same class case will trigger a DEBUG_LOCKS_WARN_ON()
in the match_held_lock() when releasing the locks.

> > Also seems I gave a wrong answer to Alan, just to clarify, the following
> > is not a deadlock to lockdep:
> > 
> > T1:
> > 	mutex_lock(P)
> > 	mutex_lock_next_lock(C1, P)
> > 	mutex_lock_next_lock(C2, P)
> > 	mutex_lock(B)
> > 
> > T2:
> > 	mutex_lock(P)
> > 	mutex_lock(B)
> > 	mutex_lock_next_lock(C1, P)
> > 	mutex_lock_next_lock(C2, P)
> > 
> 
> This should in fact complain about a CB-BC deadlock, (but I've not
> tested it, just going on memories of how I implemented it).
> 

Yes, confirmed by a selftest.

> > Because of any pair of
> > 
> > 	mutex_lock(L);
> > 	... // other locks maybe
> > 	mutex_lock_nest_lock(M, L);
> > 
> > lockdep will not add M into the dependency graph, since it's nested and
> > should be serialized by L.
> 
> We do enter M into the dependency graph, but instead ignore M-M
> recursion. Specifically so that we might catch the above deadlock vs B.

Right, I mis-read the code, which suggests I should improve it to help
the future me ;-)

FWIW, the selftests I used are as follow:

Regards,
Boqun

------------------------------->8
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index 8d24279fad05..6aadebad68c1 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -60,6 +60,7 @@ __setup("debug_locks_verbose=", setup_debug_locks_verbose);
 #define LOCKTYPE_RTMUTEX 0x20
 #define LOCKTYPE_LL	0x40
 #define LOCKTYPE_SPECIAL 0x80
+#define LOCKTYPE_NEST	0x100
 
 static struct ww_acquire_ctx t, t2;
 static struct ww_mutex o, o2, o3;
@@ -2091,14 +2092,14 @@ static void ww_test_edeadlk_acquire_wrong_slow(void)
 	ww_mutex_lock_slow(&o3, &t);
 }
 
-static void ww_test_spin_nest_unlocked(void)
+static void nest_test_spin_nest_unlocked(void)
 {
 	spin_lock_nest_lock(&lock_A, &o.base);
 	U(A);
 }
 
 /* This is not a deadlock, because we have X1 to serialize Y1 and Y2 */
-static void ww_test_spin_nest_lock(void)
+static void nest_test_spin_nest_lock(void)
 {
 	spin_lock(&lock_X1);
 	spin_lock_nest_lock(&lock_Y1, &lock_X1);
@@ -2110,6 +2111,33 @@ static void ww_test_spin_nest_lock(void)
 	spin_unlock(&lock_X1);
 }
 
+static void nest_test_spin_nest_lock_deadlock(void)
+{
+	nest_test_spin_nest_lock();
+
+	/*
+	 * Although above is not a deadlokc, but with the following code, Y1 and
+	 * A create a ABBA deadlock.
+	 */
+	spin_lock(&lock_X1);
+	spin_lock(&lock_A);
+	spin_lock_nest_lock(&lock_Y1, &lock_X1);
+	spin_lock_nest_lock(&lock_Y2, &lock_X1);
+	spin_unlock(&lock_A);
+	spin_unlock(&lock_Y2);
+	spin_unlock(&lock_Y1);
+	spin_unlock(&lock_X1);
+}
+
+/* Not the supported usage */
+static void nest_test_spin_nest_lock_same_class(void)
+{
+	spin_lock(&lock_X1);
+	spin_lock_nest_lock(&lock_X2, &lock_X1);
+	spin_unlock(&lock_X2);
+	spin_unlock(&lock_X1);
+}
+
 static void ww_test_unneeded_slow(void)
 {
 	WWAI(&t);
@@ -2323,14 +2351,6 @@ static void ww_tests(void)
 	dotest(ww_test_edeadlk_acquire_wrong_slow, FAILURE, LOCKTYPE_WW);
 	pr_cont("\n");
 
-	print_testname("spinlock nest unlocked");
-	dotest(ww_test_spin_nest_unlocked, FAILURE, LOCKTYPE_WW);
-	pr_cont("\n");
-
-	print_testname("spinlock nest test");
-	dotest(ww_test_spin_nest_lock, SUCCESS, LOCKTYPE_WW);
-	pr_cont("\n");
-
 	printk("  -----------------------------------------------------\n");
 	printk("                                 |block | try  |context|\n");
 	printk("  -----------------------------------------------------\n");
@@ -2360,6 +2380,27 @@ static void ww_tests(void)
 	pr_cont("\n");
 }
 
+static void nest_tests(void)
+{
+	printk("  --------------------------------------------------------------------------\n");
+	printk("  | nest lock tests |\n");
+	printk("  -------------------\n");
+	print_testname("spinlock nest unlocked");
+	dotest(nest_test_spin_nest_unlocked, FAILURE, LOCKTYPE_NEST);
+	pr_cont("\n");
+
+	print_testname("spinlock nest test");
+	dotest(nest_test_spin_nest_lock, SUCCESS, LOCKTYPE_NEST);
+	pr_cont("\n");
+	print_testname("spinlock nest test dead lock");
+	dotest(nest_test_spin_nest_lock_deadlock, FAILURE, LOCKTYPE_NEST);
+	pr_cont("\n");
+	print_testname("spinlock nest test dead lock");
+	dotest(nest_test_spin_nest_lock_same_class, FAILURE, LOCKTYPE_NEST);
+	pr_cont("\n");
+
+}
+
 
 /*
  * <in hardirq handler>
@@ -2966,6 +3007,8 @@ void locking_selftest(void)
 
 	ww_tests();
 
+	nest_tests();
+
 	force_read_lock_recursive = 0;
 	/*
 	 * queued_read_lock() specific test cases can be put here