Skip to contentSkip to conversation

lockdep rcu-preempt and synchronize_srcu() awareness

DISCUSSION Mathieu Desnoyers 3 participants 5 messages Feb 8, 2010 RCU

lore
Share & tools
lore

Mathieu Desnoyers

author reviewer
#0 lore raw

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

Reviewed-by Paul E. McKenney
#1 lore raw
Quoted 17 lines · 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();
Quoted 4 lines

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.

Quoted 4 lines

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 <[email protected]>
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 ]
Cc Peter Zijlstra <[email protected]>

LKML-Reference: <[email protected]>

include/linux/rcutiny.h +5 -0
index c4ba9a7..96cc307 100644
@@ -101,4 +101,9 @@ static inline void exit_rcu(void)
 {
 }
 
+static inline int rcu_preempt_depth(void)
+{
+	return 0;
+}
+
 #endif /* __LINUX_RCUTINY_H */
include/linux/rcutree.h +11 -0
index c93eee5..8044b1b 100644
@@ -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)
kernel/sched.c +1 -1
index af7dfa7..7be88a7 100644
@@ -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);
 }
#2 lore raw
In reply to Mathieu Desnoyers
Quoted 17 lines · 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();
Quoted 4 lines

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.

Quoted 3 lines

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

Quoted 82 lines

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

author reviewer
#3 lore raw
Quoted 23 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 17 lines · 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();
Quoted 4 lines

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

Quoted 8 lines

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

Quoted 93 lines
Quoted 4 lines

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

Quoted 82 lines

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

#4 lore raw
Quoted 35 lines · Mathieu Desnoyers
Quoted 23 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 17 lines · 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();
Quoted 4 lines

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

Quoted 8 lines

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:

Quoted 7 lines

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

Quoted 97 lines

Thanks,

Mathieu

Quoted 93 lines
Quoted 4 lines

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

Quoted 82 lines

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