Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1607566 > unrolled thread

deadlock in synchronize_srcu() in debugfs?

Back to article view | Back to linux.kernel

Contents

  deadlock in synchronize_srcu() in debugfs? Johannes Berg <johannes@sipsolutions.net> - 2017-03-23 16:00 +0100
    Re: deadlock in synchronize_srcu() in debugfs? Nicolai Stange <nicstange@gmail.com> - 2017-03-23 16:40 +0100
      Re: deadlock in synchronize_srcu() in debugfs? Johannes Berg <johannes@sipsolutions.net> - 2017-03-23 16:50 +0100
      Re: deadlock in synchronize_srcu() in debugfs? Johannes Berg <johannes@sipsolutions.net> - 2017-03-27 14:00 +0200
    Re: deadlock in synchronize_srcu() in debugfs? "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-03-23 16:40 +0100
      Re: deadlock in synchronize_srcu() in debugfs? Johannes Berg <johannes@sipsolutions.net> - 2017-03-23 16:50 +0100
    Re: deadlock in synchronize_srcu() in debugfs? Johannes Berg <johannes@sipsolutions.net> - 2017-03-23 16:40 +0100
      Re: deadlock in synchronize_srcu() in debugfs? Johannes Berg <johannes@sipsolutions.net> - 2017-03-24 10:00 +0100
        Re: deadlock in synchronize_srcu() in debugfs? Johannes Berg <johannes@sipsolutions.net> - 2017-03-24 10:30 +0100
          Re: deadlock in synchronize_srcu() in debugfs? "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-03-24 18:50 +0100
            Re: deadlock in synchronize_srcu() in debugfs? Johannes Berg <johannes@sipsolutions.net> - 2017-03-24 20:00 +0100
              Re: deadlock in synchronize_srcu() in debugfs? "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-03-24 20:40 +0100
                Re: deadlock in synchronize_srcu() in debugfs? "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-03-24 21:30 +0100
                  Re: deadlock in synchronize_srcu() in debugfs? Johannes Berg <johannes@sipsolutions.net> - 2017-03-27 13:20 +0200

#1607566 — deadlock in synchronize_srcu() in debugfs?

Hi,

Before I go hunting - has anyone seen a deadlock in synchronize_srcu()
in debugfs_remove() before? We're observing that with our (backported,
but very recent) driver against 4.9 (and 4.10, I think), but there are
no backports of any debugfs things so the backport itself doesn't seem
like a likely problem.

sysrq-w shows a lot of tasks blocked on various locks (e.g. RTNL), but
the ultimate problem is the wireless stack getting blocked on
debugfs_remove_recursive(), in __synchronize_srcu(), in
wait_for_completion() (while holding lots of locks, hence the other
tasks getting stuck).

Thanks,
johannes

[toc] | [next] | [standalone]

#1607630

Hi Johannes,

On Thu, Mar 23 2017, Johannes Berg wrote:

> Before I go hunting - has anyone seen a deadlock in synchronize_srcu()
> in debugfs_remove() before?

Not yet. How reproducible is this?


> We're observing that with our (backported, but very recent) driver
> against 4.9 (and 4.10, I think),

Do I understand it correctly that this driver has been backported from
4.11-rcX to 4.9/10 and that there isn't any issue with 4.11-rcX?


> but there are no backports of any debugfs things so the backport
> itself doesn't seem like a likely problem.

Right, there haven't been any SRCU related changes to debugfs after
4.8.


> sysrq-w shows a lot of tasks blocked on various locks (e.g. RTNL), but
> the ultimate problem is the wireless stack getting blocked on
> debugfs_remove_recursive(), in __synchronize_srcu(), in
> wait_for_completion() (while holding lots of locks, hence the other
> tasks getting stuck).

Could you share a complete backtrace? For example, is the
debugfs_remove_recursive() called from any debugfs file's fops and thus,
possibly from within a SRCU read side critical section?


Thanks,

Nicolai

[toc] | [prev] | [next] | [standalone]

#1607640

Hi,

> Not yet. How reproducible is this?

Apparently quite. I haven't tried myself - it happens during some
automated test that I need to analyse further.

> > We're observing that with our (backported, but very recent) driver
> > against 4.9 (and 4.10, I think),
> 
> Do I understand it correctly that this driver has been backported
> from 4.11-rcX to 4.9/10

Yes.

>  and that there isn't any issue with 4.11-rcX?

No, I can't say this, we haven't run that test.

> > but there are no backports of any debugfs things so the backport
> > itself doesn't seem like a likely problem.
> 
> Right, there haven't been any SRCU related changes to debugfs after
> 4.8.

Right.

> > sysrq-w shows a lot of tasks blocked on various locks (e.g. RTNL),
> > but
> > the ultimate problem is the wireless stack getting blocked on
> > debugfs_remove_recursive(), in __synchronize_srcu(), in
> > wait_for_completion() (while holding lots of locks, hence the other
> > tasks getting stuck).
> 
> Could you share a complete backtrace? For example, is the
> debugfs_remove_recursive() called from any debugfs file's fops and
> thus, possibly from within a SRCU read side critical section?

No, it's called from netlink:

[  884.634857] wpa_supplicant  D    0  1769   1005 0x00000000
[  884.634874]  0000000000000000 ffff8ca50633d140 ffff8ca507b219c0 ffff8ca5455d4cc0
[  884.634898]  ffff8ca54f599d98 ffff97df431c36a0 ffffffff878dadf3 ffff8ca500000001
[  884.634927]  81ed67337c8469e4 ffff8ca54f599d98 0000932a07b219c0 ffff8ca507b219c0
[  884.634952] Call Trace:
[  884.634969]  [<ffffffff878dadf3>] ? __schedule+0x303/0xb00
[  884.634985]  [<ffffffff878db62d>] schedule+0x3d/0x90
[  884.635002]  [<ffffffff878e022c>] schedule_timeout+0x2fc/0x600
[  884.635021]  [<ffffffff870e8b06>] ? mark_held_locks+0x66/0x90
[  884.635041]  [<ffffffff878e16bc>] ? _raw_spin_unlock_irq+0x2c/0x40
[  884.635059]  [<ffffffff878dc8cc>] wait_for_completion+0xdc/0x110
[  884.635073]  [<ffffffff870bff90>] ? wake_up_q+0x80/0x80
[  884.635091]  [<ffffffff8710a46e>] __synchronize_srcu+0x11e/0x1c0
[  884.635109]  [<ffffffff87109510>] ? trace_raw_output_rcu_utilization+0x60/0x60
[  884.635131]  [<ffffffff8710a542>] synchronize_srcu+0x32/0x40
[  884.635145]  [<ffffffff873899ed>] debugfs_remove_recursive+0x17d/0x190
[  884.635239]  [<ffffffffc087b3be>] ieee80211_debugfs_key_remove+0x1e/0x30 [mac80211]
[  884.635333]  [<ffffffffc0840773>] __ieee80211_key_destroy+0x1b3/0x480 [mac80211]
[  884.635440]  [<ffffffffc0841807>] ieee80211_free_sta_keys+0x117/0x170 [mac80211]
[  884.635524]  [<ffffffffc0807b0c>] __sta_info_destroy_part2+0x4c/0x200 [mac80211]
[  884.635597]  [<ffffffffc0807fbd>] __sta_info_flush+0x10d/0x1a0 [mac80211]
[  884.635706]  [<ffffffffc086634b>] ieee80211_set_disassoc+0xcb/0x530 [mac80211]
[  884.635802]  [<ffffffffc086e3b6>] ieee80211_mgd_deauth+0x2e6/0x7b0 [mac80211]
[  884.635901]  [<ffffffffc08237c8>] ieee80211_deauth+0x18/0x20 [mac80211]
[  884.636024]  [<ffffffffc0673e8f>] cfg80211_mlme_deauth+0x14f/0x3b0 [cfg80211]
[  884.636110]  [<ffffffffc0649265>] nl80211_deauthenticate+0xe5/0x130 [cfg80211]
[  884.636133]  [<ffffffff877dc52c>] genl_family_rcv_msg+0x1bc/0x370
[  884.636151]  [<ffffffff877dc6e0>] ? genl_family_rcv_msg+0x370/0x370
[  884.636262]  [<ffffffff877dc760>] genl_rcv_msg+0x80/0xc0
[  884.636275]  [<ffffffff877dba87>] netlink_rcv_skb+0xa7/0xc0
[  884.636289]  [<ffffffff877dc148>] genl_rcv+0x28/0x40
[  884.636303]  [<ffffffff877db45b>] netlink_unicast+0x15b/0x210
[  884.636318]  [<ffffffff877db82a>] netlink_sendmsg+0x31a/0x3a0
[  884.636335]  [<ffffffff8777bb48>] sock_sendmsg+0x38/0x50
[  884.636354]  [<ffffffff8777c41c>] ___sys_sendmsg+0x26c/0x280
[  884.636378]  [<ffffffff8717b042>] ? ring_buffer_unlock_commit+0x32/0x290
[  884.636393]  [<ffffffff8718122e>] ? __buffer_unlock_commit+0x1e/0x40
[  884.636407]  [<ffffffff87181d12>] ? tracing_mark_write+0x162/0x2b0
[  884.636423]  [<ffffffff870e7419>] ? __lock_is_held+0x49/0x70
[  884.636440]  [<ffffffff8777d0a5>] __sys_sendmsg+0x45/0x80
[  884.636459]  [<ffffffff8777d0f2>] SyS_sendmsg+0x12/0x20
[  884.636477]  [<ffffffff878e1e45>] entry_SYSCALL_64_fastpath+0x23/0xc6


johannes

[toc] | [prev] | [next] | [standalone]

#1609753

Hi,

> > Before I go hunting - has anyone seen a deadlock in
> > synchronize_srcu() in debugfs_remove() before?
> 
> Not yet. How reproducible is this?

So ... this turned out to be a livelock of sorts.

We have a debugfs file (not upstream (yet?), it seems) that basically
blocks reading data.

At the point of system hanging, there was a process reading from that
file, with no data being generated.

A second process was trying to remove a completely unrelated debugfs
file (*), with the RTNL held.

A third and many other processes were waiting to acquire the RTNL.


Obviously, in light of things like nfp_net_debugfs_tx_q_read(),
wil_write_file_reset(), lowpan_short_addr_get() and quite a few more,
nobody in the whole system can now remove debugfs files while holding
the RTNL. Not sure how many people that affects, but it's IMHO a pretty
major new restriction, and one that isn't even flagged at all.


Similarly, nobody should be blocking in debugfs files, like we did in
ours, but also smsdvb_stats_read(), crtc_crc_open() look like they
could block for quite a while. Again, there's no warning here that
blocking in debugfs files can now indefinitely defer completely
unrelated debugfs_remove() calls in the entire system.

Overall, while I can solve this problem for our driver, possibly by
making the debugfs file return some dummy data periodically if no real
data exists, which may not easily be possible for all such files, I'm
not convinced that all of this really is the right thing to actually
impose. Perhaps if it was per directory, or per some kind of subsystem?

johannes

(*) before removing first first we'd obviously wake up and thereby more
or less terminate the readers first

[toc] | [prev] | [next] | [standalone]

#1607634

On Thu, Mar 23, 2017 at 03:54:46PM +0100, Johannes Berg wrote:
> Hi,
> 
> Before I go hunting - has anyone seen a deadlock in synchronize_srcu()
> in debugfs_remove() before? We're observing that with our (backported,
> but very recent) driver against 4.9 (and 4.10, I think), but there are
> no backports of any debugfs things so the backport itself doesn't seem
> like a likely problem.
> 
> sysrq-w shows a lot of tasks blocked on various locks (e.g. RTNL), but
> the ultimate problem is the wireless stack getting blocked on
> debugfs_remove_recursive(), in __synchronize_srcu(), in
> wait_for_completion() (while holding lots of locks, hence the other
> tasks getting stuck).

I have not seen this, but my usual question for __synchronize_srcu()
is if some other task is blocked holding srcu_read_lock() for that
same srcu_struct.

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1607639

On Thu, 2017-03-23 at 08:37 -0700, Paul E. McKenney wrote:

> I have not seen this, but my usual question for __synchronize_srcu()
> is if some other task is blocked holding srcu_read_lock() for that
> same srcu_struct.
> 

Not as far as I can see - but that was the scenario I was outlining in
my second email, I guess.

I'll need to reproduce it and a get a fuller view of the system, I only
have the "echo w > sysrq-trigger" output right now.

Thanks,
johannes

[toc] | [prev] | [next] | [standalone]

#1607635

On Thu, 2017-03-23 at 15:54 +0100, Johannes Berg wrote:

> Before I go hunting - has anyone seen a deadlock in
> synchronize_srcu() in debugfs_remove() before?

Isn't it possible for the following to happen?

CPU1					CPU2

mutex_lock(&M);
					full_proxy_xyz();
					srcu_read_lock(&debugfs_srcu);
					real_fops->xyz();
					mutex_lock(&M);
debugfs_remove(F);
synchronize_srcu(&debugfs_srcu);

-> deadlock?

I'm not convinced that this is the scenario I'm looking at, since then
it seems I should see the mutex_lock(&M) on CPU 2 with a backtrace
pointing to a full_proxy and the debugfs operation I recognize, but
lots of debugfs files acquire locks and it seems likely that it's not
always removed without holding those locks?

Am I missing something? I'll see if I can add lockdep annotations.

johannes

[toc] | [prev] | [next] | [standalone]

#1608235

On Thu, 2017-03-23 at 16:29 +0100, Johannes Berg wrote:
> Isn't it possible for the following to happen?
> 
> CPU1					CPU2
> 
> mutex_lock(&M);
> 					full_proxy_xyz();
> 					srcu_read_lock(&debugfs_srcu);
> 					real_fops->xyz();
> 					mutex_lock(&M);
> debugfs_remove(F);
> synchronize_srcu(&debugfs_srcu);


So I'm pretty sure that this can happen. I'm not convinced that it's
happening here, but still.

I tried to make lockdep flag it, but the only way I could get it to
flag it was to do this:

--- a/include/linux/srcu.h
+++ b/include/linux/srcu.h
@@ -235,7 +235,7 @@ static inline int srcu_read_lock(struct srcu_struct *sp) __acquires(sp)
 	preempt_disable();
 	retval = __srcu_read_lock(sp);
 	preempt_enable();
-	rcu_lock_acquire(&(sp)->dep_map);
+	lock_map_acquire(&(sp)->dep_map);
 	return retval;
 }
 
@@ -249,7 +249,7 @@ static inline int srcu_read_lock(struct srcu_struct *sp) __acquires(sp)
 static inline void srcu_read_unlock(struct srcu_struct *sp, int idx)
 	__releases(sp)
 {
-	rcu_lock_release(&(sp)->dep_map);
+	lock_map_release(&(sp)->dep_map);
 	__srcu_read_unlock(sp, idx);
 }
 
diff --git a/kernel/rcu/srcu.c b/kernel/rcu/srcu.c
index ef3bcfb15b39..0f9e542ca3f2 100644
--- a/kernel/rcu/srcu.c
+++ b/kernel/rcu/srcu.c
@@ -395,6 +395,9 @@ static void __synchronize_srcu(struct srcu_struct *sp, int trycount)
 			 lock_is_held(&rcu_sched_lock_map),
 			 "Illegal synchronize_srcu() in same-type SRCU (or in RCU) read-side critical section");
 
+	lock_map_acquire(&sp->dep_map);
+	lock_map_release(&sp->dep_map);
+
 	might_sleep();
 	init_completion(&rcu.completion);
 

The lock_map_acquire() in srcu_read_lock() is really not desired
though, since it will make recursion get flagged as bad. If I change
that to lock_map_acquire_read() though, the problem doesn't get flagged
for some reason. I thought it should.


Regardless though, I don't see a way to solve this problem for debugfs.
We have a ton of debugfs files in net/mac80211/debugfs.c that need to
acquire e.g. the RTNL (or other locks), and I'm not sure we can easily
avoid removing the debugfs files under the RTNL, since we get all our
configuration callbacks with the RTNL already held...

Need to think about that, but perhaps there's some other solution?

johannes

[toc] | [prev] | [next] | [standalone]

#1608266

Hi,

On Fri, 2017-03-24 at 09:56 +0100, Johannes Berg wrote:
> On Thu, 2017-03-23 at 16:29 +0100, Johannes Berg wrote:
> > Isn't it possible for the following to happen?
> > 
> > CPU1					CPU2
> > 
> > mutex_lock(&M); // acquires mutex
> > 					full_proxy_xyz();
> > 					srcu_read_lock(&debugfs_srcu);
> > 					real_fops->xyz();
> > 					mutex_lock(&M); // waiting for mutex
> > debugfs_remove(F);
> > synchronize_srcu(&debugfs_srcu);

> So I'm pretty sure that this can happen. I'm not convinced that it's
> happening here, but still.

I'm a bit confused, in that SRCU, of course, doesn't wait until all the
readers are done - that'd be a regular reader/writer lock or something.

However, it does (have to) wait until all the currently active read-
side sections have terminated, which still leads to a deadlock in the
example above, I think?

In his 2006 LWN article Paul wrote:

    The designer of a given subsystem is responsible for: (1) ensuring
    that SRCU read-side sleeping is bounded and (2) limiting the amount
    of memory waiting for synchronize_srcu(). [1]

In the case of debugfs files acquiring locks, (1) can't really be
guaranteed, especially if those locks can be held while doing
synchronize_srcu() [via debugfs_remove], so I still think the lockdep
annotation needs to be changed to at least have some annotation at
synchronize_srcu() time so we can detect this.

Now, I still suspect there's some other bug here in the case that I'm
seeing, because I don't actually see the "mutex_lock(&M); // waiting"
piece in the traces. I'll need to run this with some tracing on Monday
when the test guys are back from the weekend.

I'm also not sure how I can possibly fix this in debugfs in mac80211
and friends, but that's perhaps a different story. Clearly, this
debugfs patch is a good thing - the code will likely have had use-
after-free problems in this situation without it. But flagging the
potential deadlocks would make it a lot easier to find them.

johannes

[toc] | [prev] | [next] | [standalone]

#1608724

On Fri, Mar 24, 2017 at 10:24:46AM +0100, Johannes Berg wrote:
> Hi,
> 
> On Fri, 2017-03-24 at 09:56 +0100, Johannes Berg wrote:
> > On Thu, 2017-03-23 at 16:29 +0100, Johannes Berg wrote:
> > > Isn't it possible for the following to happen?
> > > 
> > > CPU1					CPU2
> > > 
> > > mutex_lock(&M); // acquires mutex
> > > 					full_proxy_xyz();
> > > 					srcu_read_lock(&debugfs_srcu);
> > > 					real_fops->xyz();
> > > 					mutex_lock(&M); // waiting for mutex
> > > debugfs_remove(F);
> > > synchronize_srcu(&debugfs_srcu);
> 
> > So I'm pretty sure that this can happen. I'm not convinced that it's
> > happening here, but still.
> 
> I'm a bit confused, in that SRCU, of course, doesn't wait until all the
> readers are done - that'd be a regular reader/writer lock or something.

Agreed, synchronize_srcu()  does not have to wait for new readers
(as a reader/writer lock would), but it -does- have have to wait for
pre-existing readers, like the one shown in your example above.

> However, it does (have to) wait until all the currently active read-
> side sections have terminated, which still leads to a deadlock in the
> example above, I think?

Yes.  CPU2 has a pre-existing reader that CPU1's synchronize_srcu()
must wait for.  But CPU2's reader cannot end until CPU1 releases
its lock, which it cannot do until after CPU2's reader ends.  Thus,
as you say, deadlock.

The rule is that if you are within any kind of RCU read-side critical
section, you cannot directly or indirectly wait for a grace period from
that same RCU flavor.

> In his 2006 LWN article Paul wrote:
> 
>     The designer of a given subsystem is responsible for: (1) ensuring
>     that SRCU read-side sleeping is bounded and (2) limiting the amount
>     of memory waiting for synchronize_srcu(). [1]
> 
> In the case of debugfs files acquiring locks, (1) can't really be
> guaranteed, especially if those locks can be held while doing
> synchronize_srcu() [via debugfs_remove], so I still think the lockdep
> annotation needs to be changed to at least have some annotation at
> synchronize_srcu() time so we can detect this.

That would be very nice!

There are some challenges, though.  This is OK:

	CPU1				CPU2
	i = srcu_read_lock(&mysrcu);	mutex_lock(&my_lock);
	mutex_lock(&my_lock);		i = srcu_read_lock(&mysrcu);
	srcu_read_unlock(&mysrcu, i);	mutex_unlock(&my_lock);
	mutex_unlock(&my_lock);		srcu_read_unlock(&mysrcu, i);

	CPU3
	synchronize_srcu(&mylock);

This could be a deadlock for reader-writer locking, but not for SRCU.

This is also OK:

	CPU1				CPU2
	i = srcu_read_lock(&mysrcu);	mutex_lock(&my_lock);
	mutex_lock(&my_lock);		synchronize_srcu(&yoursrcu);
	srcu_read_unlock(&mysrcu, i);	mutex_unlock(&my_lock);
	mutex_unlock(&my_lock);

Here CPU1's read-side critical sections are for mysrcu, which is
independent of CPU2's grace period for yoursrcu.

So you could flag any lockdep cycle that contained a reader and a
synchronous grace period for the same flavor of RCU, where for SRCU the
identity of the srcu_struct structure is part of the flavor.

> Now, I still suspect there's some other bug here in the case that I'm
> seeing, because I don't actually see the "mutex_lock(&M); // waiting"
> piece in the traces. I'll need to run this with some tracing on Monday
> when the test guys are back from the weekend.
> 
> I'm also not sure how I can possibly fix this in debugfs in mac80211
> and friends, but that's perhaps a different story. Clearly, this
> debugfs patch is a good thing - the code will likely have had use-
> after-free problems in this situation without it. But flagging the
> potential deadlocks would make it a lot easier to find them.

No argument here!

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1608888

> Yes.  CPU2 has a pre-existing reader that CPU1's synchronize_srcu()
> must wait for.  But CPU2's reader cannot end until CPU1 releases
> its lock, which it cannot do until after CPU2's reader ends.  Thus,
> as you say, deadlock.
> 
> The rule is that if you are within any kind of RCU read-side critical
> section, you cannot directly or indirectly wait for a grace period
> from that same RCU flavor.

Right. This is indirect then, in a way.

> There are some challenges, though.  This is OK:
> 
>	CPU1				CPU2
>	i = srcu_read_lock(&mysrcu);	mutex_lock(&my_lock);
>	mutex_lock(&my_lock);		i = srcu_read_lock(&mysrcu);
>	srcu_read_unlock(&mysrcu, i);	mutex_unlock(&my_lock);
>	mutex_unlock(&my_lock);		srcu_read_unlock(&mysrcu, i);
> 
> 	CPU3
> 	synchronize_srcu(&mylock);
> 
> This could be a deadlock for reader-writer locking, but not for SRCU.

Hmm, yes, that's a good point. If srcu_read_lock() was read_lock, and
synchronize_srcu() was write_lock(), then the write_lock() could stop
CPU2's read_lock() from acquiring the lock, and thus cause a deadlock.

However, I'm not convinced that lockdep handles reader/writer locks
correctly to start with, right now, since it *didn't* actually trigger
any warnings when I annotated SRCU as a reader/writer lock.

> This is also OK:
>	CPU1				CPU2
>	i = srcu_read_lock(&mysrcu);	mutex_lock(&my_lock);
>	mutex_lock(&my_lock);		synchronize_srcu(&yoursrc
u);
>	srcu_read_unlock(&mysrcu, i);	mutex_unlock(&my_lock);
>	mutex_unlock(&my_lock);
> 
> Here CPU1's read-side critical sections are for mysrcu, which is
> independent of CPU2's grace period for yoursrcu.

Right, but that's already covered by having separate a lockdep_map for
each SRCU subsystem (mysrcu, yoursrcu).

> So you could flag any lockdep cycle that contained a reader and a
> synchronous grace period for the same flavor of RCU, where for SRCU
> the identity of the srcu_struct structure is part of the flavor.

Right. Basically, I think SRCU should be like a reader/writer lock
(perhaps fixed to work right). The only difference seems to be the
scenario you outlined above (first of the two)?

Actually, given the scenario above, for lockdep purposes the
reader/writer lock is actually the same as a recursive lock, I guess?

You outlined a scenario in which the reader gets blocked due to a
writer (CPU3 doing a write_lock()) so the reader can still participate
in a deadlock cycle since it can - without any other locks being held
by CPU3 that participate - cause a deadlock between CPU1 and CPU2 here.
For lockdep then, even seeing the CPU1 and CPU2 scenarios should be
sufficient to flag a deadlock (*).

This part then isn't true for SRCU, because there forward progress will
still be made. So for SRCU, the "reader" side really needs to be
connected with a "writer" side to form a deadlock cycle, unlike for a
reader/writer lock.

johannes

(*) technically only after checking that write_lock() is ever used, but
... seems reasonable enough to assume that it will be used, since why
would anyone ever use a reader/writer lock if there are only readers?
That's a no-op.

[toc] | [prev] | [next] | [standalone]

#1608936

On Fri, Mar 24, 2017 at 07:51:47PM +0100, Johannes Berg wrote:
> 
> > Yes.  CPU2 has a pre-existing reader that CPU1's synchronize_srcu()
> > must wait for.  But CPU2's reader cannot end until CPU1 releases
> > its lock, which it cannot do until after CPU2's reader ends.  Thus,
> > as you say, deadlock.
> > 
> > The rule is that if you are within any kind of RCU read-side critical
> > section, you cannot directly or indirectly wait for a grace period
> > from that same RCU flavor.
> 
> Right. This is indirect then, in a way.

Agreed, in a way.  ;-)

> > There are some challenges, though.  This is OK:
> > 
> >	CPU1				CPU2
> >	i = srcu_read_lock(&mysrcu);	mutex_lock(&my_lock);
> >	mutex_lock(&my_lock);		i = srcu_read_lock(&mysrcu);
> >	srcu_read_unlock(&mysrcu, i);	mutex_unlock(&my_lock);
> >	mutex_unlock(&my_lock);		srcu_read_unlock(&mysrcu, i);
> > 
> > 	CPU3
> > 	synchronize_srcu(&mylock);
> > 
> > This could be a deadlock for reader-writer locking, but not for SRCU.
> 
> Hmm, yes, that's a good point. If srcu_read_lock() was read_lock, and
> synchronize_srcu() was write_lock(), then the write_lock() could stop
> CPU2's read_lock() from acquiring the lock, and thus cause a deadlock.

Yes.

> However, I'm not convinced that lockdep handles reader/writer locks
> correctly to start with, right now, since it *didn't* actually trigger
> any warnings when I annotated SRCU as a reader/writer lock.

I haven't looked into lockdep enough to know either way.

> > This is also OK:
> >	CPU1				CPU2
> >	i = srcu_read_lock(&mysrcu);	mutex_lock(&my_lock);
> >	mutex_lock(&my_lock);		synchronize_srcu(&yoursrc
> u);
> >	srcu_read_unlock(&mysrcu, i);	mutex_unlock(&my_lock);
> >	mutex_unlock(&my_lock);
> > 
> > Here CPU1's read-side critical sections are for mysrcu, which is
> > independent of CPU2's grace period for yoursrcu.
> 
> Right, but that's already covered by having separate a lockdep_map for
> each SRCU subsystem (mysrcu, yoursrcu).

I hope so, but haven't proved that this would work in all possible cases.

> > So you could flag any lockdep cycle that contained a reader and a
> > synchronous grace period for the same flavor of RCU, where for SRCU
> > the identity of the srcu_struct structure is part of the flavor.
> 
> Right. Basically, I think SRCU should be like a reader/writer lock
> (perhaps fixed to work right). The only difference seems to be the
> scenario you outlined above (first of the two)?
> 
> Actually, given the scenario above, for lockdep purposes the
> reader/writer lock is actually the same as a recursive lock, I guess?

Except that a recursive reader/writer lock can still have deadlocks
involving the outermost reader that would not be deadlocks for the
equivalent SRCU scenarios.

> You outlined a scenario in which the reader gets blocked due to a
> writer (CPU3 doing a write_lock()) so the reader can still participate
> in a deadlock cycle since it can - without any other locks being held
> by CPU3 that participate - cause a deadlock between CPU1 and CPU2 here.
> For lockdep then, even seeing the CPU1 and CPU2 scenarios should be
> sufficient to flag a deadlock (*).

Might this be one of the reasons why lockdep has problems with
reader-writer locks?

> This part then isn't true for SRCU, because there forward progress will
> still be made. So for SRCU, the "reader" side really needs to be
> connected with a "writer" side to form a deadlock cycle, unlike for a
> reader/writer lock.

Yes, for SRCU, srcu_read_lock() itself never blocks, so it never
participates directly in a deadlock cycle.  It has to be the case
that something within the SRCU read-side critical section blocks
and takes its place in the deadlock cycle.

Then again, if you didn't have something blocking within your SRCU
read-side critical section, why would you be using SRCU instead of
just plain RCU?  ;-)

> johannes
> 
> (*) technically only after checking that write_lock() is ever used, but
> ... seems reasonable enough to assume that it will be used, since why
> would anyone ever use a reader/writer lock if there are only readers?
> That's a no-op.

Makes sense to me!  The only reasons I can come up with are things like
shutting lockdep up when it wants a given lock read-held or some such.

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1608954

On Fri, Mar 24, 2017 at 12:33:22PM -0700, Paul E. McKenney wrote:
> On Fri, Mar 24, 2017 at 07:51:47PM +0100, Johannes Berg wrote:
> > 
> > > Yes.  CPU2 has a pre-existing reader that CPU1's synchronize_srcu()
> > > must wait for.  But CPU2's reader cannot end until CPU1 releases
> > > its lock, which it cannot do until after CPU2's reader ends.  Thus,
> > > as you say, deadlock.
> > > 
> > > The rule is that if you are within any kind of RCU read-side critical
> > > section, you cannot directly or indirectly wait for a grace period
> > > from that same RCU flavor.
> > 
> > Right. This is indirect then, in a way.
> 
> Agreed, in a way.  ;-)
> 
> > > There are some challenges, though.  This is OK:
> > > 
> > >	CPU1				CPU2
> > >	i = srcu_read_lock(&mysrcu);	mutex_lock(&my_lock);
> > >	mutex_lock(&my_lock);		i = srcu_read_lock(&mysrcu);
> > >	srcu_read_unlock(&mysrcu, i);	mutex_unlock(&my_lock);
> > >	mutex_unlock(&my_lock);		srcu_read_unlock(&mysrcu, i);
> > > 
> > > 	CPU3
> > > 	synchronize_srcu(&mylock);
> > > 
> > > This could be a deadlock for reader-writer locking, but not for SRCU.
> > 
> > Hmm, yes, that's a good point. If srcu_read_lock() was read_lock, and
> > synchronize_srcu() was write_lock(), then the write_lock() could stop
> > CPU2's read_lock() from acquiring the lock, and thus cause a deadlock.
> 
> Yes.
> 
> > However, I'm not convinced that lockdep handles reader/writer locks
> > correctly to start with, right now, since it *didn't* actually trigger
> > any warnings when I annotated SRCU as a reader/writer lock.
> 
> I haven't looked into lockdep enough to know either way.
> 
> > > This is also OK:
> > >	CPU1				CPU2
> > >	i = srcu_read_lock(&mysrcu);	mutex_lock(&my_lock);
> > >	mutex_lock(&my_lock);		synchronize_srcu(&yoursrc
> > u);
> > >	srcu_read_unlock(&mysrcu, i);	mutex_unlock(&my_lock);
> > >	mutex_unlock(&my_lock);
> > > 
> > > Here CPU1's read-side critical sections are for mysrcu, which is
> > > independent of CPU2's grace period for yoursrcu.
> > 
> > Right, but that's already covered by having separate a lockdep_map for
> > each SRCU subsystem (mysrcu, yoursrcu).
> 
> I hope so, but haven't proved that this would work in all possible cases.
> 
> > > So you could flag any lockdep cycle that contained a reader and a
> > > synchronous grace period for the same flavor of RCU, where for SRCU
> > > the identity of the srcu_struct structure is part of the flavor.
> > 
> > Right. Basically, I think SRCU should be like a reader/writer lock
> > (perhaps fixed to work right). The only difference seems to be the
> > scenario you outlined above (first of the two)?
> > 
> > Actually, given the scenario above, for lockdep purposes the
> > reader/writer lock is actually the same as a recursive lock, I guess?
> 
> Except that a recursive reader/writer lock can still have deadlocks
> involving the outermost reader that would not be deadlocks for the
> equivalent SRCU scenarios.
> 
> > You outlined a scenario in which the reader gets blocked due to a
> > writer (CPU3 doing a write_lock()) so the reader can still participate
> > in a deadlock cycle since it can - without any other locks being held
> > by CPU3 that participate - cause a deadlock between CPU1 and CPU2 here.
> > For lockdep then, even seeing the CPU1 and CPU2 scenarios should be
> > sufficient to flag a deadlock (*).
> 
> Might this be one of the reasons why lockdep has problems with
> reader-writer locks?
> 
> > This part then isn't true for SRCU, because there forward progress will
> > still be made. So for SRCU, the "reader" side really needs to be
> > connected with a "writer" side to form a deadlock cycle, unlike for a
> > reader/writer lock.
> 
> Yes, for SRCU, srcu_read_lock() itself never blocks, so it never
> participates directly in a deadlock cycle.  It has to be the case
> that something within the SRCU read-side critical section blocks
> and takes its place in the deadlock cycle.
> 
> Then again, if you didn't have something blocking within your SRCU
> read-side critical section, why would you be using SRCU instead of
> just plain RCU?  ;-)
> 
> > johannes
> > 
> > (*) technically only after checking that write_lock() is ever used, but
> > ... seems reasonable enough to assume that it will be used, since why
> > would anyone ever use a reader/writer lock if there are only readers?
> > That's a no-op.
> 
> Makes sense to me!  The only reasons I can come up with are things like
> shutting lockdep up when it wants a given lock read-held or some such.

And I cannot resist adding this one:

	CPU 1				CPU 2
	i = srcu_read_lock(&s1);	mutex_lock(&l1);
	mutex_lock(&l1);		synchronize_srcu(&s2);
	mutex_unlock(&l1);		mutex_unlock(&l1);
	srcu_read_unlock(&s1, i);

	CPU 3				CPU 4
	i = srcu_read_lock(&s2);	mutex_lock(&l2);
	mutex_lock(&l2);		synchronize_srcu(&s1);
	mutex_unlock(&l2);		mutex_unlock(&l2);
	srcu_read_unlock(&s2, i);

Removing the SRCU statements from any of these CPU would break the
deadlock.  This can be easily extended to a deadlock cycle involving
any number of srcu_struct structures.

But this would still be a cycle involving an srcu_read_lock() and a
synchronize_srcu() on the same srcu_struct, which is reassuring.

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1609742

On Fri, 2017-03-24 at 13:20 -0700, Paul E. McKenney wrote:
> 
> And I cannot resist adding this one:
> 
> 	CPU 1				CPU 2
> 	i = srcu_read_lock(&s1);	mutex_lock(&l1);
> 	mutex_lock(&l1);		synchronize_srcu(&s2);
> 	mutex_unlock(&l1);		mutex_unlock(&l1);
> 	srcu_read_unlock(&s1, i);
> 
> 	CPU 3				CPU 4
> 	i = srcu_read_lock(&s2);	mutex_lock(&l2);
> 	mutex_lock(&l2);		synchronize_srcu(&s1);
> 	mutex_unlock(&l2);		mutex_unlock(&l2);
> 	srcu_read_unlock(&s2, i);
> 
> Removing the SRCU statements from any of these CPU would break the
> deadlock.  This can be easily extended to a deadlock cycle involving
> any number of srcu_struct structures.
> 
> But this would still be a cycle involving an srcu_read_lock() and a
> synchronize_srcu() on the same srcu_struct, which is reassuring.

Right, you can cycle this indefinitely. lockdep has some kind of
maximum chain length I think. :)

johannes

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web