lockdep rcu-preempt and synchronize_srcu() awareness

lockdep rcu-preempt and synchronize_srcu() awareness

[Mathieu Desnoyers]

Hi,

I just though about the following deadlock scenario involving rcu preempt and
mutexes. I see that lockdep does not warn about it, and it actually triggers a
deadlock on my box. It might be worth addressing for TREE_PREEMPT_RCU configs.

CPU A:
    mutex_lock(&test_mutex);
    synchronize_rcu();
    mutex_unlock(&test_mutex);

CPU B:
    rcu_read_lock();
    mutex_lock(&test_mutex);
    mutex_unlock(&test_mutex);
    rcu_read_unlock();

But given that it's not legit to take a mutex from within a rcu read lock in
non-preemptible configs, I guess it's not much of a real-life problem, but I
think SRCU is also affected, because there is no lockdep annotation around
synchronize_srcu().

So I think it would be good to mark rcu_read_lock/unlock as not permitting
"might_sleep()" in non preemptable RCU configs, and having a look at lockdep
SRCU support might be worthwhile.

The following test module triggers the problem:


/* test-rcu-lockdep.c
 *
 * Test RCU-awareness of lockdep. Don't look at the interface, it's aweful.
 * run, in parallel:
 *
 * cat /proc/testa 
 * cat /proc/testb
 */

#include <linux/module.h>
#include <linux/mutex.h>
#include <linux/proc_fs.h>
#include <linux/sched.h>
#include <linux/delay.h>

struct proc_dir_entry *pentrya = NULL;
struct proc_dir_entry *pentryb = NULL;

static DEFINE_MUTEX(test_mutex);

static int my_opena(struct inode *inode, struct file *file)
{
	mutex_lock(&test_mutex);
	synchronize_rcu();
	mutex_unlock(&test_mutex);

	return -EPERM;
}


static struct file_operations my_operationsa = {
	.open = my_opena,
};

static int my_openb(struct inode *inode, struct file *file)
{
	rcu_read_lock();
	mutex_lock(&test_mutex);
	ssleep(1);
	mutex_unlock(&test_mutex);
	rcu_read_unlock();


	return -EPERM;
}


static struct file_operations my_operationsb = {
	.open = my_openb,
};

int init_module(void)
{
	pentrya = create_proc_entry("testa", 0444, NULL);
	if (pentrya)
		pentrya->proc_fops = &my_operationsa;

	pentryb = create_proc_entry("testb", 0444, NULL);
	if (pentryb)
		pentryb->proc_fops = &my_operationsb;

	return 0;
}

void cleanup_module(void)
{
	remove_proc_entry("testa", NULL);
	remove_proc_entry("testb", NULL);
}

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Mathieu Desnoyers");
MODULE_DESCRIPTION("lockdep rcu test");



Thanks,

Mathieu

Re: lockdep rcu-preempt and synchronize_srcu() awareness

[Peter Zijlstra]

On Mon, 2010-02-08 at 14:18 -0500, Mathieu Desnoyers wrote:
> Hi,
> 
> I just though about the following deadlock scenario involving rcu preempt and
> mutexes. I see that lockdep does not warn about it, and it actually triggers a
> deadlock on my box. It might be worth addressing for TREE_PREEMPT_RCU configs.
> 
> CPU A:
>     mutex_lock(&test_mutex);
>     synchronize_rcu();
>     mutex_unlock(&test_mutex);
> 
> CPU B:
>     rcu_read_lock();
>     mutex_lock(&test_mutex);
>     mutex_unlock(&test_mutex);
>     rcu_read_unlock();
> 
> But given that it's not legit to take a mutex from within a rcu read lock in
> non-preemptible configs, I guess it's not much of a real-life problem, but I
> think SRCU is also affected, because there is no lockdep annotation around
> synchronize_srcu().

Right, even if there were, the lockdep rcu_read_lock annotation is
check==1, lockdep needs significant work to properly deal with fully
recursive locks such as rcu_read_lock(), the read side of rwlock_t and
cpu-hotplug.

Both ego and myself have been poking at that at various times but never
followed through, I think the last series is:
  http://lkml.org/lkml/2009/5/11/203

Once we have lock_acquire(.check=2, .read=2) working properly, adding
the above annotation is trivial, basically add:

	lock_acquire(&rcu_lock_map, 0, 0, 0, 2, NULL, _THIS_IP_);
	lock_release(&rcu_lock_map, 0, _THIS_IP_);

To the various synchronize_*() primitives with the respective lock_map.

> 
> So I think it would be good to mark rcu_read_lock/unlock as not permitting
> "might_sleep()" in non preemptable RCU configs, and having a look at lockdep
> SRCU support might be worthwhile.

commit 234da7bcdc7aaa935846534c3b726dbc79a9cdd5
Author: Frederic Weisbecker <fweisbec@gmail.com>
Date:   Wed Dec 16 20:21:05 2009 +0100

    sched: Teach might_sleep() about preemptible RCU
    
    In practice, it is harmless to voluntarily sleep in a
    rcu_read_lock() section if we are running under preempt rcu, but
    it is illegal if we build a kernel running non-preemptable rcu.
    
    Currently, might_sleep() doesn't notice sleepable operations
    under rcu_read_lock() sections if we are running under
    preemptable rcu because preempt_count() is left untouched after
    rcu_read_lock() in this case. But we want developers who test
    their changes under such config to notice the "sleeping while
    atomic" issues.
    
    So we add rcu_read_lock_nesting to prempt_count() in
    might_sleep() checks.
    
    [ v2: Handle rcu-tiny ]
    Signed-off-by: Frederic Weisbecker <fweisbec@gmail.com>
    Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
    Cc: Peter Zijlstra <peterz@infradead.org>
    LKML-Reference: <1260991265-8451-1-git-send-regression-fweisbec@gmail.com>
    Signed-off-by: Ingo Molnar <mingo@elte.hu>

diff --git a/include/linux/rcutiny.h b/include/linux/rcutiny.h
index c4ba9a7..96cc307 100644
--- a/include/linux/rcutiny.h
+++ b/include/linux/rcutiny.h
@@ -101,4 +101,9 @@ static inline void exit_rcu(void)
 {
 }
 
+static inline int rcu_preempt_depth(void)
+{
+	return 0;
+}
+
 #endif /* __LINUX_RCUTINY_H */
diff --git a/include/linux/rcutree.h b/include/linux/rcutree.h
index c93eee5..8044b1b 100644
--- a/include/linux/rcutree.h
+++ b/include/linux/rcutree.h
@@ -45,6 +45,12 @@ extern void __rcu_read_unlock(void);
 extern void synchronize_rcu(void);
 extern void exit_rcu(void);
 
+/*
+ * Defined as macro as it is a very low level header
+ * included from areas that don't even know about current
+ */
+#define rcu_preempt_depth() (current->rcu_read_lock_nesting)
+
 #else /* #ifdef CONFIG_TREE_PREEMPT_RCU */
 
 static inline void __rcu_read_lock(void)
@@ -63,6 +69,11 @@ static inline void exit_rcu(void)
 {
 }
 
+static inline int rcu_preempt_depth(void)
+{
+	return 0;
+}
+
 #endif /* #else #ifdef CONFIG_TREE_PREEMPT_RCU */
 
 static inline void __rcu_read_lock_bh(void)
diff --git a/kernel/sched.c b/kernel/sched.c
index af7dfa7..7be88a7 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -9682,7 +9682,7 @@ void __init sched_init(void)
 #ifdef CONFIG_DEBUG_SPINLOCK_SLEEP
 static inline int preempt_count_equals(int preempt_offset)
 {
-	int nested = preempt_count() & ~PREEMPT_ACTIVE;
+	int nested = (preempt_count() & ~PREEMPT_ACTIVE) + rcu_preempt_depth();
 
 	return (nested == PREEMPT_INATOMIC_BASE + preempt_offset);
 }

Re: lockdep rcu-preempt and synchronize_srcu() awareness

[Paul E. McKenney]

On Mon, Feb 08, 2010 at 02:18:58PM -0500, Mathieu Desnoyers wrote:
> Hi,
> 
> I just though about the following deadlock scenario involving rcu preempt and
> mutexes. I see that lockdep does not warn about it, and it actually triggers a
> deadlock on my box. It might be worth addressing for TREE_PREEMPT_RCU configs.
> 
> CPU A:
>     mutex_lock(&test_mutex);
>     synchronize_rcu();
>     mutex_unlock(&test_mutex);
> 
> CPU B:
>     rcu_read_lock();
>     mutex_lock(&test_mutex);
>     mutex_unlock(&test_mutex);
>     rcu_read_unlock();
> 
> But given that it's not legit to take a mutex from within a rcu read lock in
> non-preemptible configs, I guess it's not much of a real-life problem, but I
> think SRCU is also affected, because there is no lockdep annotation around
> synchronize_srcu().

Indeed, doing this with SRCU would result in deadlock, and it is quite
legal to acquire mutexes from within SRCU read-side critical sections.
And similar deadlocks can be constructed using pthread_mutex_lock() and
user-space RCU implementations.

The basic rule is "don't wait for a grace period to complete while in
the corresponding flavor of RCU read-side critical section".  Your point,
that it is possible to wait indirectly, is well taken.

> So I think it would be good to mark rcu_read_lock/unlock as not permitting
> "might_sleep()" in non preemptable RCU configs, and having a look at lockdep
> SRCU support might be worthwhile.

Given the in-progress lockdep enhancements to RCU, the information is at
least present.  I can easily check for the direct case, but must defer
to Peter Z on the indirect case.

							Thanx, Paul

> The following test module triggers the problem:
> 
> 
> /* test-rcu-lockdep.c
>  *
>  * Test RCU-awareness of lockdep. Don't look at the interface, it's aweful.
>  * run, in parallel:
>  *
>  * cat /proc/testa 
>  * cat /proc/testb
>  */
> 
> #include <linux/module.h>
> #include <linux/mutex.h>
> #include <linux/proc_fs.h>
> #include <linux/sched.h>
> #include <linux/delay.h>
> 
> struct proc_dir_entry *pentrya = NULL;
> struct proc_dir_entry *pentryb = NULL;
> 
> static DEFINE_MUTEX(test_mutex);
> 
> static int my_opena(struct inode *inode, struct file *file)
> {
> 	mutex_lock(&test_mutex);
> 	synchronize_rcu();
> 	mutex_unlock(&test_mutex);
> 
> 	return -EPERM;
> }
> 
> 
> static struct file_operations my_operationsa = {
> 	.open = my_opena,
> };
> 
> static int my_openb(struct inode *inode, struct file *file)
> {
> 	rcu_read_lock();
> 	mutex_lock(&test_mutex);
> 	ssleep(1);
> 	mutex_unlock(&test_mutex);
> 	rcu_read_unlock();
> 
> 
> 	return -EPERM;
> }
> 
> 
> static struct file_operations my_operationsb = {
> 	.open = my_openb,
> };
> 
> int init_module(void)
> {
> 	pentrya = create_proc_entry("testa", 0444, NULL);
> 	if (pentrya)
> 		pentrya->proc_fops = &my_operationsa;
> 
> 	pentryb = create_proc_entry("testb", 0444, NULL);
> 	if (pentryb)
> 		pentryb->proc_fops = &my_operationsb;
> 
> 	return 0;
> }
> 
> void cleanup_module(void)
> {
> 	remove_proc_entry("testa", NULL);
> 	remove_proc_entry("testb", NULL);
> }
> 
> MODULE_LICENSE("GPL");
> MODULE_AUTHOR("Mathieu Desnoyers");
> MODULE_DESCRIPTION("lockdep rcu test");
> 
> 
> 
> Thanks,
> 
> Mathieu

Re: lockdep rcu-preempt and synchronize_srcu() awareness

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> On Mon, Feb 08, 2010 at 02:18:58PM -0500, Mathieu Desnoyers wrote:
> > Hi,
> > 
> > I just though about the following deadlock scenario involving rcu preempt and
> > mutexes. I see that lockdep does not warn about it, and it actually triggers a
> > deadlock on my box. It might be worth addressing for TREE_PREEMPT_RCU configs.
> > 
> > CPU A:
> >     mutex_lock(&test_mutex);
> >     synchronize_rcu();
> >     mutex_unlock(&test_mutex);
> > 
> > CPU B:
> >     rcu_read_lock();
> >     mutex_lock(&test_mutex);
> >     mutex_unlock(&test_mutex);
> >     rcu_read_unlock();
> > 
> > But given that it's not legit to take a mutex from within a rcu read lock in
> > non-preemptible configs, I guess it's not much of a real-life problem, but I
> > think SRCU is also affected, because there is no lockdep annotation around
> > synchronize_srcu().
> 
> Indeed, doing this with SRCU would result in deadlock, and it is quite
> legal to acquire mutexes from within SRCU read-side critical sections.
> And similar deadlocks can be constructed using pthread_mutex_lock() and
> user-space RCU implementations.
> 
> The basic rule is "don't wait for a grace period to complete while in
> the corresponding flavor of RCU read-side critical section".  Your point,
> that it is possible to wait indirectly, is well taken.

Meanwhile, I'll add this to the Userspace RCU README:

Interaction with mutexes

        One must be careful to do not cause deadlocks due to interaction of
        synchronize_rcu() and RCU read-side with mutexes. If synchronize_rcu()
        is called with a mutex held, this mutex (or any mutex which has this
        mutex in its dependency chain) should not be acquired from within a RCU
        read-side critical section.

Thanks,

Mathieu

> 
> > So I think it would be good to mark rcu_read_lock/unlock as not permitting
> > "might_sleep()" in non preemptable RCU configs, and having a look at lockdep
> > SRCU support might be worthwhile.
> 
> Given the in-progress lockdep enhancements to RCU, the information is at
> least present.  I can easily check for the direct case, but must defer
> to Peter Z on the indirect case.
> 
> 							Thanx, Paul
> 
> > The following test module triggers the problem:
> > 
> > 
> > /* test-rcu-lockdep.c
> >  *
> >  * Test RCU-awareness of lockdep. Don't look at the interface, it's aweful.
> >  * run, in parallel:
> >  *
> >  * cat /proc/testa 
> >  * cat /proc/testb
> >  */
> > 
> > #include <linux/module.h>
> > #include <linux/mutex.h>
> > #include <linux/proc_fs.h>
> > #include <linux/sched.h>
> > #include <linux/delay.h>
> > 
> > struct proc_dir_entry *pentrya = NULL;
> > struct proc_dir_entry *pentryb = NULL;
> > 
> > static DEFINE_MUTEX(test_mutex);
> > 
> > static int my_opena(struct inode *inode, struct file *file)
> > {
> > 	mutex_lock(&test_mutex);
> > 	synchronize_rcu();
> > 	mutex_unlock(&test_mutex);
> > 
> > 	return -EPERM;
> > }
> > 
> > 
> > static struct file_operations my_operationsa = {
> > 	.open = my_opena,
> > };
> > 
> > static int my_openb(struct inode *inode, struct file *file)
> > {
> > 	rcu_read_lock();
> > 	mutex_lock(&test_mutex);
> > 	ssleep(1);
> > 	mutex_unlock(&test_mutex);
> > 	rcu_read_unlock();
> > 
> > 
> > 	return -EPERM;
> > }
> > 
> > 
> > static struct file_operations my_operationsb = {
> > 	.open = my_openb,
> > };
> > 
> > int init_module(void)
> > {
> > 	pentrya = create_proc_entry("testa", 0444, NULL);
> > 	if (pentrya)
> > 		pentrya->proc_fops = &my_operationsa;
> > 
> > 	pentryb = create_proc_entry("testb", 0444, NULL);
> > 	if (pentryb)
> > 		pentryb->proc_fops = &my_operationsb;
> > 
> > 	return 0;
> > }
> > 
> > void cleanup_module(void)
> > {
> > 	remove_proc_entry("testa", NULL);
> > 	remove_proc_entry("testb", NULL);
> > }
> > 
> > MODULE_LICENSE("GPL");
> > MODULE_AUTHOR("Mathieu Desnoyers");
> > MODULE_DESCRIPTION("lockdep rcu test");
> > 
> > 
> > 
> > Thanks,
> > 
> > Mathieu

Re: lockdep rcu-preempt and synchronize_srcu() awareness

[Paul E. McKenney]

On Mon, Feb 08, 2010 at 04:57:48PM -0500, Mathieu Desnoyers wrote:
> * Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> > On Mon, Feb 08, 2010 at 02:18:58PM -0500, Mathieu Desnoyers wrote:
> > > Hi,
> > > 
> > > I just though about the following deadlock scenario involving rcu preempt and
> > > mutexes. I see that lockdep does not warn about it, and it actually triggers a
> > > deadlock on my box. It might be worth addressing for TREE_PREEMPT_RCU configs.
> > > 
> > > CPU A:
> > >     mutex_lock(&test_mutex);
> > >     synchronize_rcu();
> > >     mutex_unlock(&test_mutex);
> > > 
> > > CPU B:
> > >     rcu_read_lock();
> > >     mutex_lock(&test_mutex);
> > >     mutex_unlock(&test_mutex);
> > >     rcu_read_unlock();
> > > 
> > > But given that it's not legit to take a mutex from within a rcu read lock in
> > > non-preemptible configs, I guess it's not much of a real-life problem, but I
> > > think SRCU is also affected, because there is no lockdep annotation around
> > > synchronize_srcu().
> > 
> > Indeed, doing this with SRCU would result in deadlock, and it is quite
> > legal to acquire mutexes from within SRCU read-side critical sections.
> > And similar deadlocks can be constructed using pthread_mutex_lock() and
> > user-space RCU implementations.
> > 
> > The basic rule is "don't wait for a grace period to complete while in
> > the corresponding flavor of RCU read-side critical section".  Your point,
> > that it is possible to wait indirectly, is well taken.
> 
> Meanwhile, I'll add this to the Userspace RCU README:
> 
> Interaction with mutexes
> 
>         One must be careful to do not cause deadlocks due to interaction of
>         synchronize_rcu() and RCU read-side with mutexes. If synchronize_rcu()
>         is called with a mutex held, this mutex (or any mutex which has this
>         mutex in its dependency chain) should not be acquired from within a RCU
>         read-side critical section.

Looks good to me!

							Thanx, Paul

> Thanks,
> 
> Mathieu
> 
> > 
> > > So I think it would be good to mark rcu_read_lock/unlock as not permitting
> > > "might_sleep()" in non preemptable RCU configs, and having a look at lockdep
> > > SRCU support might be worthwhile.
> > 
> > Given the in-progress lockdep enhancements to RCU, the information is at
> > least present.  I can easily check for the direct case, but must defer
> > to Peter Z on the indirect case.
> > 
> > 							Thanx, Paul
> > 
> > > The following test module triggers the problem:
> > > 
> > > 
> > > /* test-rcu-lockdep.c
> > >  *
> > >  * Test RCU-awareness of lockdep. Don't look at the interface, it's aweful.
> > >  * run, in parallel:
> > >  *
> > >  * cat /proc/testa 
> > >  * cat /proc/testb
> > >  */
> > > 
> > > #include <linux/module.h>
> > > #include <linux/mutex.h>
> > > #include <linux/proc_fs.h>
> > > #include <linux/sched.h>
> > > #include <linux/delay.h>
> > > 
> > > struct proc_dir_entry *pentrya = NULL;
> > > struct proc_dir_entry *pentryb = NULL;
> > > 
> > > static DEFINE_MUTEX(test_mutex);
> > > 
> > > static int my_opena(struct inode *inode, struct file *file)
> > > {
> > > 	mutex_lock(&test_mutex);
> > > 	synchronize_rcu();
> > > 	mutex_unlock(&test_mutex);
> > > 
> > > 	return -EPERM;
> > > }
> > > 
> > > 
> > > static struct file_operations my_operationsa = {
> > > 	.open = my_opena,
> > > };
> > > 
> > > static int my_openb(struct inode *inode, struct file *file)
> > > {
> > > 	rcu_read_lock();
> > > 	mutex_lock(&test_mutex);
> > > 	ssleep(1);
> > > 	mutex_unlock(&test_mutex);
> > > 	rcu_read_unlock();
> > > 
> > > 
> > > 	return -EPERM;
> > > }
> > > 
> > > 
> > > static struct file_operations my_operationsb = {
> > > 	.open = my_openb,
> > > };
> > > 
> > > int init_module(void)
> > > {
> > > 	pentrya = create_proc_entry("testa", 0444, NULL);
> > > 	if (pentrya)
> > > 		pentrya->proc_fops = &my_operationsa;
> > > 
> > > 	pentryb = create_proc_entry("testb", 0444, NULL);
> > > 	if (pentryb)
> > > 		pentryb->proc_fops = &my_operationsb;
> > > 
> > > 	return 0;
> > > }
> > > 
> > > void cleanup_module(void)
> > > {
> > > 	remove_proc_entry("testa", NULL);
> > > 	remove_proc_entry("testb", NULL);
> > > }
> > > 
> > > MODULE_LICENSE("GPL");
> > > MODULE_AUTHOR("Mathieu Desnoyers");
> > > MODULE_DESCRIPTION("lockdep rcu test");
> > > 
> > > 
> > > 
> > > Thanks,
> > > 
> > > Mathieu