Re: possible deadlock in __ata_sff_interrupt

Re: possible deadlock in __ata_sff_interrupt

[Damien Le Moal]

On 12/14/22 00:09, Wei Chen wrote:
> Dear Linux Developer,
> 
> Recently, when using our tool to fuzz kernel, the following crash was triggered.
> 
> HEAD commit: 094226ad94f4 Linux v6.1-rc5
> git tree: upstream
> compiler: clang 12.0.1
> console output:
> https://drive.google.com/file/d/1QZttkbuLed4wp6U32UR6TpxfY_HHCIqQ/view?usp=share_link
> kernel config: https://drive.google.com/file/d/1TdPsg_5Zon8S2hEFpLBWjb8Tnd2KA5WJ/view?usp=share_link
> 
> Unfortunately, I didn't have a reproducer for this crash yet.
> 
> IMPORTANT: if you fix the bug, please add the following tag to the commit:
> Reported-by: Wei Chen <harperchen1110@gmail.com>
> 
> =====================================================
> WARNING: HARDIRQ-safe -> HARDIRQ-unsafe lock order detected
> 6.1.0-rc5 #40 Not tainted
> -----------------------------------------------------
> syz-executor.0/27911 [HC0[0]:SC0[0]:HE0:SE1] is trying to acquire:
> ffff888076cc4f30 (&new->fa_lock){....}-{2:2}, at: kill_fasync_rcu
> fs/fcntl.c:996 [inline]
> ffff888076cc4f30 (&new->fa_lock){....}-{2:2}, at:
> kill_fasync+0x13b/0x430 fs/fcntl.c:1017

[...]

> stack backtrace:
> CPU: 0 PID: 27911 Comm: syz-executor.0 Not tainted 6.1.0-rc5 #40
> Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS
> 1.13.0-1ubuntu1.1 04/01/2014
> Call Trace:
>  <TASK>
>  __dump_stack lib/dump_stack.c:88 [inline]
>  dump_stack_lvl+0x1b1/0x28e lib/dump_stack.c:106
>  print_bad_irq_dependency kernel/locking/lockdep.c:2611 [inline]
>  check_irq_usage kernel/locking/lockdep.c:2850 [inline]
>  check_prev_add kernel/locking/lockdep.c:3101 [inline]
>  check_prevs_add+0x4e5f/0x5b70 kernel/locking/lockdep.c:3216
>  validate_chain kernel/locking/lockdep.c:3831 [inline]
>  __lock_acquire+0x4411/0x6070 kernel/locking/lockdep.c:5055
>  lock_acquire+0x17f/0x430 kernel/locking/lockdep.c:5668
>  __raw_read_lock_irqsave include/linux/rwlock_api_smp.h:160 [inline]
>  _raw_read_lock_irqsave+0xbb/0x100 kernel/locking/spinlock.c:236
>  kill_fasync_rcu fs/fcntl.c:996 [inline]
>  kill_fasync+0x13b/0x430 fs/fcntl.c:1017
>  sg_rq_end_io+0x604/0xf50 drivers/scsi/sg.c:1403

The problem is here: sg_rq_end_io() calling kill_fasync(). But at a quick
glance, this is not the only driver calling kill_fasync() with a spinlock
held with irq disabled... So there may be a fundamental problem with
kill_fasync() function if drivers are allowed to do that, or the reverse,
all drivers calling that function with a lock held with irq disabled need
to be fixed.

Al, Chuck, Jeff,

Any thought ?

>  __blk_mq_end_request+0x2c7/0x380 block/blk-mq.c:1011
>  scsi_end_request+0x4ed/0x9c0 drivers/scsi/scsi_lib.c:576
>  scsi_io_completion+0xc25/0x27a0 drivers/scsi/scsi_lib.c:985
>  ata_scsi_simulate+0x336e/0x3dd0 drivers/ata/libata-scsi.c:4190
>  __ata_scsi_queuecmd+0x20b/0x1020 drivers/ata/libata-scsi.c:4009
>  ata_scsi_queuecmd+0xa0/0x130 drivers/ata/libata-scsi.c:4052
>  scsi_dispatch_cmd drivers/scsi/scsi_lib.c:1524 [inline]
>  scsi_queue_rq+0x1ea6/0x2ec0 drivers/scsi/scsi_lib.c:1760
>  blk_mq_dispatch_rq_list+0x104f/0x2ca0 block/blk-mq.c:1992
>  __blk_mq_sched_dispatch_requests+0x382/0x490 block/blk-mq-sched.c:306
>  blk_mq_sched_dispatch_requests+0xef/0x160 block/blk-mq-sched.c:339
>  __blk_mq_run_hw_queue+0x1cf/0x260 block/blk-mq.c:2110
>  blk_mq_sched_insert_request+0x1e2/0x430 block/blk-mq-sched.c:458
>  blk_execute_rq_nowait+0x2e8/0x3b0 block/blk-mq.c:1305
>  sg_common_write+0x8c0/0x1970 drivers/scsi/sg.c:832
>  sg_new_write+0x61f/0x860 drivers/scsi/sg.c:770
>  sg_ioctl_common drivers/scsi/sg.c:935 [inline]
>  sg_ioctl+0x1c51/0x2be0 drivers/scsi/sg.c:1159
>  vfs_ioctl fs/ioctl.c:51 [inline]
>  __do_sys_ioctl fs/ioctl.c:870 [inline]
>  __se_sys_ioctl+0xfb/0x170 fs/ioctl.c:856
>  do_syscall_x64 arch/x86/entry/common.c:50 [inline]
>  do_syscall_64+0x3d/0x90 arch/x86/entry/common.c:80
>  entry_SYSCALL_64_after_hwframe+0x63/0xcd
> RIP: 0033:0x7f153dc8bded
> Code: 02 b8 ff ff ff ff c3 66 0f 1f 44 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 c7 c1 bc ff ff ff f7 d8 64 89 01 48
> RSP: 002b:00007f153ede2c58 EFLAGS: 00000246 ORIG_RAX: 0000000000000010
> RAX: ffffffffffffffda RBX: 00007f153ddabf80 RCX: 00007f153dc8bded
> RDX: 0000000020000440 RSI: 0000000000002285 RDI: 0000000000000006
> RBP: 00007f153dcf8ce0 R08: 0000000000000000 R09: 0000000000000000
> R10: 0000000000000000 R11: 0000000000000246 R12: 00007f153ddabf80
> R13: 00007ffc72e5108f R14: 00007ffc72e51230 R15: 00007f153ede2dc0
>  </TASK>
> 
> Best,
> Wei

-- 
Damien Le Moal
Western Digital Research

Re: possible deadlock in __ata_sff_interrupt

[Al Viro]

On Thu, Dec 15, 2022 at 06:48:20PM +0900, Damien Le Moal wrote:

> The problem is here: sg_rq_end_io() calling kill_fasync(). But at a quick
> glance, this is not the only driver calling kill_fasync() with a spinlock
> held with irq disabled... So there may be a fundamental problem with
> kill_fasync() function if drivers are allowed to do that, or the reverse,
> all drivers calling that function with a lock held with irq disabled need
> to be fixed.
> 
> Al, Chuck, Jeff,
> 
> Any thought ?

What is the problem with read_lock_irqsave() called with irqs disabled?
read_lock_irq() would have been a bug in such conditions, of course, but
that's not what we use...

Re: possible deadlock in __ata_sff_interrupt

[Damien Le Moal]

On 12/16/22 00:19, Al Viro wrote:
> On Thu, Dec 15, 2022 at 06:48:20PM +0900, Damien Le Moal wrote:
> 
>> The problem is here: sg_rq_end_io() calling kill_fasync(). But at a quick
>> glance, this is not the only driver calling kill_fasync() with a spinlock
>> held with irq disabled... So there may be a fundamental problem with
>> kill_fasync() function if drivers are allowed to do that, or the reverse,
>> all drivers calling that function with a lock held with irq disabled need
>> to be fixed.
>>
>> Al, Chuck, Jeff,
>>
>> Any thought ?
> 
> What is the problem with read_lock_irqsave() called with irqs disabled?
> read_lock_irq() would have been a bug in such conditions, of course, but
> that's not what we use...

The original & complete lockdep splat is in the report email here:

https://marc.info/?l=linux-ide&m=167094379710177&w=2

It looks like a spinlock is taken for the fasync stuff without irq
disabled and that same spinlock is needed in kill_fasync() which is
itself called (potentially) with IRQ disabled. Hence the splat. In any
case, that is how I understand the issue. But as mentioned above, given
that I can see many drivers calling kill_fasync() with irq disabled, I
wonder if this is a genuine potential problem or a false negative.

-- 
Damien Le Moal
Western Digital Research

Re: possible deadlock in __ata_sff_interrupt

[Al Viro]

On Fri, Dec 16, 2022 at 10:44:06AM +0900, Damien Le Moal wrote:

> The original & complete lockdep splat is in the report email here:
> 
> https://marc.info/?l=linux-ide&m=167094379710177&w=2
> 
> It looks like a spinlock is taken for the fasync stuff without irq
> disabled and that same spinlock is needed in kill_fasync() which is
> itself called (potentially) with IRQ disabled. Hence the splat. In any
> case, that is how I understand the issue. But as mentioned above, given
> that I can see many drivers calling kill_fasync() with irq disabled, I
> wonder if this is a genuine potential problem or a false negative.

OK, I'm about to fall asleep, so I might very well be missing something
obvious, but...

CPU1: ptrace(2)
	ptrace_check_attach()
		read_lock(&tasklist_lock);

CPU2: setpgid(2)
        write_lock_irq(&tasklist_lock);
	spins

CPU1: takes an interrupt that would call kill_fasync().  grep and the
first instance of kill_fasync() is in hpet_interrupt() - it's not
something exotic.  IRQs disabled on CPU2 won't stop it.
	kill_fasync(..., SIGIO, ...)
		kill_fasync_rcu()
			read_lock_irqsave(&fa->fa_lock, flags);
			send_sigio()
			        read_lock_irqsave(&fown->lock, flags);
		                read_lock(&tasklist_lock);

... and CPU1 spins as well.

It's not a matter of kill_fasync() called with IRQs disabled; the
problem is kill_fasync() called from interrupt taken while holding
tasklist_lock at least shared.  Somebody trying to grab it on another
CPU exclusive before we get to send_sigio() from kill_fasync() will
end up spinning and will make us spin as well.

I really hope that's just me not seeing something obvious - we had
kill_fasync() called in IRQ handlers since way back and we had
tasklist_lock taken shared without disabling IRQs for just as long.

<goes to sleep, hoping to find "Al, you are a moron, it's obviously OK
for such and such reasons" in the mailbox tomorrow morning>

Re: possible deadlock in __ata_sff_interrupt

[Linus Torvalds]

On Thu, Dec 15, 2022 at 7:41 PM Al Viro <viro@zeniv.linux.org.uk> wrote:
>
> CPU1: ptrace(2)
>         ptrace_check_attach()
>                 read_lock(&tasklist_lock);
>
> CPU2: setpgid(2)
>         write_lock_irq(&tasklist_lock);
>         spins
>
> CPU1: takes an interrupt that would call kill_fasync().  grep and the
> first instance of kill_fasync() is in hpet_interrupt() - it's not
> something exotic.  IRQs disabled on CPU2 won't stop it.
>         kill_fasync(..., SIGIO, ...)
>                 kill_fasync_rcu()
>                         read_lock_irqsave(&fa->fa_lock, flags);
>                         send_sigio()
>                                 read_lock_irqsave(&fown->lock, flags);
>                                 read_lock(&tasklist_lock);
>
> ... and CPU1 spins as well.

Nope. See kernel/locking/qrwlock.c:

        /*
         * Readers come here when they cannot get the lock without waiting
         */
        if (unlikely(in_interrupt())) {
                /*
                 * Readers in interrupt context will get the lock immediately
                 * if the writer is just waiting (not holding the lock yet),
                 * so spin with ACQUIRE semantics until the lock is available
                 * without waiting in the queue.
                 */
                atomic_cond_read_acquire(&lock->cnts, !(VAL & _QW_LOCKED));
                return;
        }

and that's the new "civilized" reader unfairness.

The traditional rwlock was unconditionally unfair to writers, to the
point that there were starvation issues because new readers would
always get the lock.

         Linus

Re: possible deadlock in __ata_sff_interrupt

[Al Viro]

[Boqun Feng Cc'd]

On Fri, Dec 16, 2022 at 03:26:21AM -0800, Linus Torvalds wrote:
> On Thu, Dec 15, 2022 at 7:41 PM Al Viro <viro@zeniv.linux.org.uk> wrote:
> >
> > CPU1: ptrace(2)
> >         ptrace_check_attach()
> >                 read_lock(&tasklist_lock);
> >
> > CPU2: setpgid(2)
> >         write_lock_irq(&tasklist_lock);
> >         spins
> >
> > CPU1: takes an interrupt that would call kill_fasync().  grep and the
> > first instance of kill_fasync() is in hpet_interrupt() - it's not
> > something exotic.  IRQs disabled on CPU2 won't stop it.
> >         kill_fasync(..., SIGIO, ...)
> >                 kill_fasync_rcu()
> >                         read_lock_irqsave(&fa->fa_lock, flags);
> >                         send_sigio()
> >                                 read_lock_irqsave(&fown->lock, flags);
> >                                 read_lock(&tasklist_lock);
> >
> > ... and CPU1 spins as well.
> 
> Nope. See kernel/locking/qrwlock.c:

[snip rwlocks are inherently unfair, queued ones are somewhat milder, but
all implementations have writers-starving behaviour for read_lock() at least
when in_interrupt()]

D'oh...  Consider requested "Al, you are a moron" duly delivered...  I plead
having been on way too low caffeine and too little sleep ;-/

Looking at the original report, looks like the scenario there is meant to be
the following:

CPU1: read_lock(&tasklist_lock)
	tasklist_lock grabbed

CPU2: get an sg write(2) feeding request to libata; host->lock is taken,
	request is immediately completed and scsi_done() is about to be called.
	host->lock grabbed

CPU3: write_lock_irq(&tasklist_lock)
	spins on tasklist_lock until CPU1 gets through.

CPU2: get around to kill_fasync() called by sg_rq_end_io() and to grabbing
	tasklist_lock inside send_sigio()
	spins, since it's not in an interrupt and there's a pending writer
	host->lock is held, spin until CPU3 gets through.

CPU1: take an interrupt, which on libata will try to grab host->lock
	tasklist_lock is held, spins on host->lock until CPU2 gets through

Am I reading it correctly?

Re: possible deadlock in __ata_sff_interrupt

[Boqun Feng]

On Fri, Dec 16, 2022 at 11:39:21PM +0000, Al Viro wrote:
> [Boqun Feng Cc'd]
> 
> On Fri, Dec 16, 2022 at 03:26:21AM -0800, Linus Torvalds wrote:
> > On Thu, Dec 15, 2022 at 7:41 PM Al Viro <viro@zeniv.linux.org.uk> wrote:
> > >
> > > CPU1: ptrace(2)
> > >         ptrace_check_attach()
> > >                 read_lock(&tasklist_lock);
> > >
> > > CPU2: setpgid(2)
> > >         write_lock_irq(&tasklist_lock);
> > >         spins
> > >
> > > CPU1: takes an interrupt that would call kill_fasync().  grep and the
> > > first instance of kill_fasync() is in hpet_interrupt() - it's not
> > > something exotic.  IRQs disabled on CPU2 won't stop it.
> > >         kill_fasync(..., SIGIO, ...)
> > >                 kill_fasync_rcu()
> > >                         read_lock_irqsave(&fa->fa_lock, flags);
> > >                         send_sigio()
> > >                                 read_lock_irqsave(&fown->lock, flags);
> > >                                 read_lock(&tasklist_lock);
> > >
> > > ... and CPU1 spins as well.
> > 
> > Nope. See kernel/locking/qrwlock.c:
> 
> [snip rwlocks are inherently unfair, queued ones are somewhat milder, but
> all implementations have writers-starving behaviour for read_lock() at least
> when in_interrupt()]
> 
> D'oh...  Consider requested "Al, you are a moron" duly delivered...  I plead
> having been on way too low caffeine and too little sleep ;-/
> 
> Looking at the original report, looks like the scenario there is meant to be
> the following:
> 
> CPU1: read_lock(&tasklist_lock)
> 	tasklist_lock grabbed
> 
> CPU2: get an sg write(2) feeding request to libata; host->lock is taken,
> 	request is immediately completed and scsi_done() is about to be called.
> 	host->lock grabbed
> 
> CPU3: write_lock_irq(&tasklist_lock)
> 	spins on tasklist_lock until CPU1 gets through.
> 
> CPU2: get around to kill_fasync() called by sg_rq_end_io() and to grabbing
> 	tasklist_lock inside send_sigio()
> 	spins, since it's not in an interrupt and there's a pending writer
> 	host->lock is held, spin until CPU3 gets through.

Right, for a reader not in_interrupt(), it may be blocked by a random
waiting writer because of the fairness, even the lock is currently held
by a reader:

	CPU 1			CPU 2		CPU 3
	read_lock(&tasklist_lock); // get the lock

						write_lock_irq(&tasklist_lock); // wait for the lock

				read_lock(&tasklist_lock); // cannot get the lock because of the fairness

Regards,
Boqun

> 
> CPU1: take an interrupt, which on libata will try to grab host->lock
> 	tasklist_lock is held, spins on host->lock until CPU2 gets through
> 
> Am I reading it correctly?

Re: possible deadlock in __ata_sff_interrupt

[Al Viro]

On Fri, Dec 16, 2022 at 03:54:09PM -0800, Boqun Feng wrote:
> On Fri, Dec 16, 2022 at 11:39:21PM +0000, Al Viro wrote:
> > [Boqun Feng Cc'd]
> > 
> > On Fri, Dec 16, 2022 at 03:26:21AM -0800, Linus Torvalds wrote:
> > > On Thu, Dec 15, 2022 at 7:41 PM Al Viro <viro@zeniv.linux.org.uk> wrote:
> > > >
> > > > CPU1: ptrace(2)
> > > >         ptrace_check_attach()
> > > >                 read_lock(&tasklist_lock);
> > > >
> > > > CPU2: setpgid(2)
> > > >         write_lock_irq(&tasklist_lock);
> > > >         spins
> > > >
> > > > CPU1: takes an interrupt that would call kill_fasync().  grep and the
> > > > first instance of kill_fasync() is in hpet_interrupt() - it's not
> > > > something exotic.  IRQs disabled on CPU2 won't stop it.
> > > >         kill_fasync(..., SIGIO, ...)
> > > >                 kill_fasync_rcu()
> > > >                         read_lock_irqsave(&fa->fa_lock, flags);
> > > >                         send_sigio()
> > > >                                 read_lock_irqsave(&fown->lock, flags);
> > > >                                 read_lock(&tasklist_lock);
> > > >
> > > > ... and CPU1 spins as well.
> > > 
> > > Nope. See kernel/locking/qrwlock.c:
> > 
> > [snip rwlocks are inherently unfair, queued ones are somewhat milder, but
> > all implementations have writers-starving behaviour for read_lock() at least
> > when in_interrupt()]
> > 
> > D'oh...  Consider requested "Al, you are a moron" duly delivered...  I plead
> > having been on way too low caffeine and too little sleep ;-/
> > 
> > Looking at the original report, looks like the scenario there is meant to be
> > the following:
> > 
> > CPU1: read_lock(&tasklist_lock)
> > 	tasklist_lock grabbed
> > 
> > CPU2: get an sg write(2) feeding request to libata; host->lock is taken,
> > 	request is immediately completed and scsi_done() is about to be called.
> > 	host->lock grabbed
> > 
> > CPU3: write_lock_irq(&tasklist_lock)
> > 	spins on tasklist_lock until CPU1 gets through.
> > 
> > CPU2: get around to kill_fasync() called by sg_rq_end_io() and to grabbing
> > 	tasklist_lock inside send_sigio()
> > 	spins, since it's not in an interrupt and there's a pending writer
> > 	host->lock is held, spin until CPU3 gets through.
> 
> Right, for a reader not in_interrupt(), it may be blocked by a random
> waiting writer because of the fairness, even the lock is currently held
> by a reader:
> 
> 	CPU 1			CPU 2		CPU 3
> 	read_lock(&tasklist_lock); // get the lock
> 
> 						write_lock_irq(&tasklist_lock); // wait for the lock
> 
> 				read_lock(&tasklist_lock); // cannot get the lock because of the fairness

IOW, any caller of scsi_done() from non-interrupt context while
holding a spinlock that is also taken in an interrupt...

And we have drivers/scsi/scsi_error.c:scsi_send_eh_cmnd(), which calls
->queuecommand() under a mutex, with
#define DEF_SCSI_QCMD(func_name) \
        int func_name(struct Scsi_Host *shost, struct scsi_cmnd *cmd)   \
        {                                                               \
                unsigned long irq_flags;                                \
                int rc;                                                 \
                spin_lock_irqsave(shost->host_lock, irq_flags);         \
                rc = func_name##_lck(cmd);                              \
                spin_unlock_irqrestore(shost->host_lock, irq_flags);    \
                return rc;                                              \
        }

being commonly used for ->queuecommand() instances.  So any scsi_done()
in foo_lck() (quite a few of such) + use of ->host_lock in interrupt
for the same driver (also common)...

I wonder why that hadn't triggered the same warning a long time
ago - these warnings had been around for at least two years.

Am I missing something here?

Re: possible deadlock in __ata_sff_interrupt

[Linus Torvalds]

Ok, let's bring in Waiman for the rwlock side.

On Fri, Dec 16, 2022 at 5:54 PM Boqun Feng <boqun.feng@gmail.com> wrote:
>
> Right, for a reader not in_interrupt(), it may be blocked by a random
> waiting writer because of the fairness, even the lock is currently held
> by a reader:
>
>         CPU 1                   CPU 2           CPU 3
>         read_lock(&tasklist_lock); // get the lock
>
>                                                 write_lock_irq(&tasklist_lock); // wait for the lock
>
>                                 read_lock(&tasklist_lock); // cannot get the lock because of the fairness

But this should be ok - because CPU1 can make progress and eventually
release the lock.

So the tasklist_lock use is fine on its own - the reason interrupts
are special is because an interrupt on CPU 1 taking the lock for
reading would deadlock otherwise. As long as it happens on another
CPU, the original CPU should then be able to make progress.

But the problem here seems to be thst *another* lock is also involved
(in this case apparently "host->lock", and now if CPU1 and CPU2 get
these two locks in a different order, you can get an ABBA deadlock.

And apparently our lockdep machinery doesn't catch that issue, so it
doesn't get flagged.

I'm not sure what the lockdep rules for rwlocks are, but maybe lockdep
treats rwlocks as being _always_ unfair, not knowing about that "it's
only unfair when it's in interrupt context".

Maybe we need to always make rwlock unfair? Possibly only for tasklist_lock?

Oh, how I hate tasklist_lock. It's pretty much our one remaining "one
big lock". It's been a pain for a long long time.

            Linus

Re: possible deadlock in __ata_sff_interrupt

[Boqun Feng]

On Fri, Dec 16, 2022 at 08:31:54PM -0600, Linus Torvalds wrote:
> Ok, let's bring in Waiman for the rwlock side.
> 
> On Fri, Dec 16, 2022 at 5:54 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> >
> > Right, for a reader not in_interrupt(), it may be blocked by a random
> > waiting writer because of the fairness, even the lock is currently held
> > by a reader:
> >
> >         CPU 1                   CPU 2           CPU 3
> >         read_lock(&tasklist_lock); // get the lock
> >
> >                                                 write_lock_irq(&tasklist_lock); // wait for the lock
> >
> >                                 read_lock(&tasklist_lock); // cannot get the lock because of the fairness
> 
> But this should be ok - because CPU1 can make progress and eventually
> release the lock.
> 

Yes.

> So the tasklist_lock use is fine on its own - the reason interrupts
> are special is because an interrupt on CPU 1 taking the lock for
> reading would deadlock otherwise. As long as it happens on another
> CPU, the original CPU should then be able to make progress.
> 
> But the problem here seems to be thst *another* lock is also involved
> (in this case apparently "host->lock", and now if CPU1 and CPU2 get
> these two locks in a different order, you can get an ABBA deadlock.
> 

Right.

> And apparently our lockdep machinery doesn't catch that issue, so it
> doesn't get flagged.
> 

I'm confused. Isn't the original problem showing that lockdep catches
this?

> I'm not sure what the lockdep rules for rwlocks are, but maybe lockdep
> treats rwlocks as being _always_ unfair, not knowing about that "it's
> only unfair when it's in interrupt context".
> 

The rules nowadays are:

*	If the reader is in_interrupt() or queued-spinlock implemention
	is not used, it's an unfair reader, i.e. it won't wait for
	any existing writer.

*	Otherwise, it's a fair reader.

> Maybe we need to always make rwlock unfair? Possibly only for tasklist_lock?
> 

That's possible, but I need to make sure I understand the issue for
lockdep. It's that lockdep misses catching something or it has a false
positive?

Regards,
Boqun

> Oh, how I hate tasklist_lock. It's pretty much our one remaining "one
> big lock". It's been a pain for a long long time.
> 
>             Linus

Re: possible deadlock in __ata_sff_interrupt

[Al Viro]

On Fri, Dec 16, 2022 at 08:31:54PM -0600, Linus Torvalds wrote:
> Ok, let's bring in Waiman for the rwlock side.
> 
> On Fri, Dec 16, 2022 at 5:54 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> >
> > Right, for a reader not in_interrupt(), it may be blocked by a random
> > waiting writer because of the fairness, even the lock is currently held
> > by a reader:
> >
> >         CPU 1                   CPU 2           CPU 3
> >         read_lock(&tasklist_lock); // get the lock
> >
> >                                                 write_lock_irq(&tasklist_lock); // wait for the lock
> >
> >                                 read_lock(&tasklist_lock); // cannot get the lock because of the fairness
> 
> But this should be ok - because CPU1 can make progress and eventually
> release the lock.
> 
> So the tasklist_lock use is fine on its own - the reason interrupts
> are special is because an interrupt on CPU 1 taking the lock for
> reading would deadlock otherwise. As long as it happens on another
> CPU, the original CPU should then be able to make progress.
> 
> But the problem here seems to be thst *another* lock is also involved
> (in this case apparently "host->lock", and now if CPU1 and CPU2 get
> these two locks in a different order, you can get an ABBA deadlock.
> 
> And apparently our lockdep machinery doesn't catch that issue, so it
> doesn't get flagged.

Lockdep has actually caught that; the locks involved are mention in the
report (https://marc.info/?l=linux-ide&m=167094379710177&w=2).  The form
of report might have been better, but if anything, it doesn't mention
potential involvement of tasklist_lock writer, turning that into a deadlock.

OTOH, that's more or less implicit for the entire class:

read_lock(A)		[non-interrupt]
			local_irq_disable()	local_irq_disable()
			spin_lock(B)		write_lock(A)
			read_lock(A)
[in interrupt]
spin_lock(B)

is what that sort of reports is about.  In this case A is tasklist_lock,
B is host->lock.  Possible call chains for CPU1 and CPU2 are reported...

I wonder why analogues of that hadn't been reported for other SCSI hosts -
it's a really common pattern there...

> I'm not sure what the lockdep rules for rwlocks are, but maybe lockdep
> treats rwlocks as being _always_ unfair, not knowing about that "it's
> only unfair when it's in interrupt context".
> 
> Maybe we need to always make rwlock unfair? Possibly only for tasklist_lock?

ISTR threads about the possibility of explicit read_lock_unfair()...

Re: possible deadlock in __ata_sff_interrupt

[Boqun Feng]

On Sat, Dec 17, 2022 at 01:59:32AM +0000, Al Viro wrote:
> On Fri, Dec 16, 2022 at 03:54:09PM -0800, Boqun Feng wrote:
> > On Fri, Dec 16, 2022 at 11:39:21PM +0000, Al Viro wrote:
> > > [Boqun Feng Cc'd]
> > > 
> > > On Fri, Dec 16, 2022 at 03:26:21AM -0800, Linus Torvalds wrote:
> > > > On Thu, Dec 15, 2022 at 7:41 PM Al Viro <viro@zeniv.linux.org.uk> wrote:
> > > > >
> > > > > CPU1: ptrace(2)
> > > > >         ptrace_check_attach()
> > > > >                 read_lock(&tasklist_lock);
> > > > >
> > > > > CPU2: setpgid(2)
> > > > >         write_lock_irq(&tasklist_lock);
> > > > >         spins
> > > > >
> > > > > CPU1: takes an interrupt that would call kill_fasync().  grep and the
> > > > > first instance of kill_fasync() is in hpet_interrupt() - it's not
> > > > > something exotic.  IRQs disabled on CPU2 won't stop it.
> > > > >         kill_fasync(..., SIGIO, ...)
> > > > >                 kill_fasync_rcu()
> > > > >                         read_lock_irqsave(&fa->fa_lock, flags);
> > > > >                         send_sigio()
> > > > >                                 read_lock_irqsave(&fown->lock, flags);
> > > > >                                 read_lock(&tasklist_lock);
> > > > >
> > > > > ... and CPU1 spins as well.
> > > > 
> > > > Nope. See kernel/locking/qrwlock.c:
> > > 
> > > [snip rwlocks are inherently unfair, queued ones are somewhat milder, but
> > > all implementations have writers-starving behaviour for read_lock() at least
> > > when in_interrupt()]
> > > 
> > > D'oh...  Consider requested "Al, you are a moron" duly delivered...  I plead
> > > having been on way too low caffeine and too little sleep ;-/
> > > 
> > > Looking at the original report, looks like the scenario there is meant to be
> > > the following:
> > > 
> > > CPU1: read_lock(&tasklist_lock)
> > > 	tasklist_lock grabbed
> > > 
> > > CPU2: get an sg write(2) feeding request to libata; host->lock is taken,
> > > 	request is immediately completed and scsi_done() is about to be called.
> > > 	host->lock grabbed
> > > 
> > > CPU3: write_lock_irq(&tasklist_lock)
> > > 	spins on tasklist_lock until CPU1 gets through.
> > > 
> > > CPU2: get around to kill_fasync() called by sg_rq_end_io() and to grabbing
> > > 	tasklist_lock inside send_sigio()
> > > 	spins, since it's not in an interrupt and there's a pending writer
> > > 	host->lock is held, spin until CPU3 gets through.
> > 
> > Right, for a reader not in_interrupt(), it may be blocked by a random
> > waiting writer because of the fairness, even the lock is currently held
> > by a reader:
> > 
> > 	CPU 1			CPU 2		CPU 3
> > 	read_lock(&tasklist_lock); // get the lock
> > 
> > 						write_lock_irq(&tasklist_lock); // wait for the lock
> > 
> > 				read_lock(&tasklist_lock); // cannot get the lock because of the fairness
> 
> IOW, any caller of scsi_done() from non-interrupt context while
> holding a spinlock that is also taken in an interrupt...
> 
> And we have drivers/scsi/scsi_error.c:scsi_send_eh_cmnd(), which calls
> ->queuecommand() under a mutex, with
> #define DEF_SCSI_QCMD(func_name) \
>         int func_name(struct Scsi_Host *shost, struct scsi_cmnd *cmd)   \
>         {                                                               \
>                 unsigned long irq_flags;                                \
>                 int rc;                                                 \
>                 spin_lock_irqsave(shost->host_lock, irq_flags);         \
>                 rc = func_name##_lck(cmd);                              \
>                 spin_unlock_irqrestore(shost->host_lock, irq_flags);    \
>                 return rc;                                              \
>         }
> 
> being commonly used for ->queuecommand() instances.  So any scsi_done()
> in foo_lck() (quite a few of such) + use of ->host_lock in interrupt
> for the same driver (also common)...
> 
> I wonder why that hadn't triggered the same warning a long time
> ago - these warnings had been around for at least two years.
> 

FWIW, the complete dependency chain is:

	&host->lock --> &new->fa_lock --> &f->f_owner.lock --> tasklist_lock

for the "&f->f_owner.lock" part to get into lockdep's radar, the
following call trace needs to appear once:

	kill_fasync():
	  kill_fasync_rcu():
	    send_sigio()

not sure whether it's rare or not though. And ->fa_lock also had its own
issue:

	https://lore.kernel.org/lkml/20210702091831.615042-1-desmondcheongzx@gmail.com/

which may have covered &host->lock for a while ;-)

Regards,
Boqun

> Am I missing something here?

Re: possible deadlock in __ata_sff_interrupt

[Waiman Long]

On 12/16/22 22:05, Al Viro wrote:
> On Fri, Dec 16, 2022 at 08:31:54PM -0600, Linus Torvalds wrote:
>> Ok, let's bring in Waiman for the rwlock side.
>>
>> On Fri, Dec 16, 2022 at 5:54 PM Boqun Feng <boqun.feng@gmail.com> wrote:
>>> Right, for a reader not in_interrupt(), it may be blocked by a random
>>> waiting writer because of the fairness, even the lock is currently held
>>> by a reader:
>>>
>>>          CPU 1                   CPU 2           CPU 3
>>>          read_lock(&tasklist_lock); // get the lock
>>>
>>>                                                  write_lock_irq(&tasklist_lock); // wait for the lock
>>>
>>>                                  read_lock(&tasklist_lock); // cannot get the lock because of the fairness
>> But this should be ok - because CPU1 can make progress and eventually
>> release the lock.
>>
>> So the tasklist_lock use is fine on its own - the reason interrupts
>> are special is because an interrupt on CPU 1 taking the lock for
>> reading would deadlock otherwise. As long as it happens on another
>> CPU, the original CPU should then be able to make progress.
>>
>> But the problem here seems to be thst *another* lock is also involved
>> (in this case apparently "host->lock", and now if CPU1 and CPU2 get
>> these two locks in a different order, you can get an ABBA deadlock.
>>
>> And apparently our lockdep machinery doesn't catch that issue, so it
>> doesn't get flagged.
> Lockdep has actually caught that; the locks involved are mention in the
> report (https://marc.info/?l=linux-ide&m=167094379710177&w=2).  The form
> of report might have been better, but if anything, it doesn't mention
> potential involvement of tasklist_lock writer, turning that into a deadlock.
>
> OTOH, that's more or less implicit for the entire class:
>
> read_lock(A)		[non-interrupt]
> 			local_irq_disable()	local_irq_disable()
> 			spin_lock(B)		write_lock(A)
> 			read_lock(A)
> [in interrupt]
> spin_lock(B)
>
> is what that sort of reports is about.  In this case A is tasklist_lock,
> B is host->lock.  Possible call chains for CPU1 and CPU2 are reported...
>
> I wonder why analogues of that hadn't been reported for other SCSI hosts -
> it's a really common pattern there...
>
>> I'm not sure what the lockdep rules for rwlocks are, but maybe lockdep
>> treats rwlocks as being _always_ unfair, not knowing about that "it's
>> only unfair when it's in interrupt context".
>>
>> Maybe we need to always make rwlock unfair? Possibly only for tasklist_lock?
That may not be a good idea as the cacheline bouncing problem will be 
back with reduced performance.
> ISTR threads about the possibility of explicit read_lock_unfair()...

Another possible alternative is to treat the read_lock as unfair if 
interrupt has been disabled as I think we should reduce the interrupt 
disabled interval as much as possible.

Thought?

Cheers,
Longman