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

Groups > linux.kernel > #1325660 > unrolled thread

[RFC 0/6] Track RCU dereferences in RCU read-side critical sections

Back to article view | Back to linux.kernel

Contents

  [RFC 0/6] Track RCU dereferences in RCU read-side critical sections Boqun Feng <boqun.feng@gmail.com> - 2016-02-03 17:50 +0100
    [RFC 3/6] lockdep: LOCKED_ACCESS: Maintain the keys of acqchains Boqun Feng <boqun.feng@gmail.com> - 2016-02-03 17:50 +0100
    [RFC 4/6] lockdep: LOCKED_ACCESS: Introduce locked_access_point() Boqun Feng <boqun.feng@gmail.com> - 2016-02-03 17:50 +0100
    [RFC 5/6] lockdep: LOCKED_ACCESS: Add proc interface for locked access class Boqun Feng <boqun.feng@gmail.com> - 2016-02-03 17:50 +0100

#1325660 — [RFC 0/6] Track RCU dereferences in RCU read-side critical sections

As a characteristic of RCU, read-side critical sections have a very
loose connection with rcu_dereference()s, which is you can only be sure
about an rcu_dereference() might be called in some read-side critical
section, but if code gets complex, you may not be sure which read-side
critical section exactly, this might be also an problem for some other
locking mechanisms, that is the critical sections protecting data and
the data accesses protected are not clearly correlated.

In this series, we are introducing LOCKED_ACCESS framework and based on
which, we implement the RCU_LOCKED_ACCESS functionality to give us a
clear hint: which rcu_dereference() happens in which RCU read-side
critical section. 

The basic idea of LOCKED_ACCESS is to maintain a chain of locks we have
acquired already, and when there happens a data access, correlate the
data access with the chain.

Lockdep already has lock chains, but we introduce a new but similar one
concept: acqchain, an acqchain is similar to a lock chain, except that
the key of an acqchain is the hash sum of the acquire (instruction)
positions of the locks in the chain, whereas the key of a lock chain is
the hash sum of the class keys of the locks in the chain.

Acqchains are introduced because we want to correlate data accesses with
critical sections and critical sections are better represented by the
acquire positions rather than lock classes.

The acqchain key of a task is maintained in the same way as lock chain
keys in lockdep.

Similar as lockdep, LOCKED_ACCESS also classify locks and data accesses
by groups, locked access class is introduced for this reason. A locked
access class also contains the data for allocation and lookup of
acqchains and accesses, and the address of a locked access class is used
as its key. By tagging locks and data accesses with the keys, we could
describe which locks and data accesses are related.

The entry point of LOCKED_ACCESS is locked_access_point(). Calling
locked_access_point() indicates that a data access happens, and after it
called the data access will be correlated with the current acqchain.

We also provide a /proc filesystem interface to show the information
we've collected, for each locked access class with the name <name> there
will be a file at /proc/locked_access/<name> showing all the
relationships collected so far for this locked access classes.

Based on LOCKED_ACCESS, we implement RCU_LOCKED_ACCESS, that tracks
rcu_dereference()s inside RCU read-side critical sections.

This patchset is based on v4.5-rc2 and consists of 6 patches(in which
patch 2-5 are the implementation of LOCKED_ACCESS):

1.	Introduce some functions of irq_context.

2.	Introduce locked access class and acqchain.

3.	Maintain the keys of acqchains.

4.	Introduce the entry point of LOCKED_ACCESS.

5.	Add proc interface for locked access class

6.	Enables LOCKED_ACCESS for RCU.

Tested by 0day and I also did a simple test on x86: build and boot a
kernel with RCU_LOCKED_ACCESS=y and CONFIG_PROVE_LOCKING=y and ran
several workloads(kernel building, git cloning, dbench), no problem has
been observed, and /proc/locked_access/rcu was able to collect the
relationships between ~300 RCU read-critical sections and ~500
rcu_dereference*().

Snippets of /proc/locked_access/rcu are as follow:

...(this rcu_dereference() happens after one rcu_read_lock())
...
ACQCHAIN 0xfdbf0c6aeea, 1 locks, irq_context 0:
  LOCK at [<ffffffff812b1115>] get_proc_task_net+0x5/0x140
    ACCESS TYPE 1 at kernel/pid.c:441
...
...(this rcu_dereference() happens after three rcu_read_lock())
...
ACQCHAIN 0xfe042af3bbfb2605, 3 locks, irq_context 0:
  LOCK at [<ffffffff81094b47>] SyS_kill+0x97/0x2a0
    LOCK at [<ffffffff8109286f>] kill_pid_info+0x1f/0x140
      LOCK at [<ffffffff81092605>] group_send_sig_info+0x5/0x130
        ACCESS TYPE 1 at kernel/signal.c:695
...

Looking forwards to any suggestion, comment and question ;-)

Regards,
Boqun

[toc] | [next] | [standalone]

#1325661 — [RFC 3/6] lockdep: LOCKED_ACCESS: Maintain the keys of acqchains

Add held_lock::prev_acqchain_key and task_struct::curr_acqchain_key to
maintain the keys of acqchains as the same as what lockdep does for
keys of lock classes.

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 include/linux/lockdep.h  |  3 +++
 include/linux/sched.h    |  3 +++
 kernel/fork.c            |  3 +++
 kernel/locking/lockdep.c | 31 +++++++++++++++++++++++++++++++
 4 files changed, 40 insertions(+)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 140c1c3..2ffe6c3 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -244,6 +244,9 @@ struct held_lock {
 	 * with zero), here we store the previous hash value:
 	 */
 	u64				prev_chain_key;
+#ifdef CONFIG_LOCKED_ACCESS
+	u64				prev_acqchain_key;
+#endif
 	unsigned long			acquire_ip;
 	struct lockdep_map		*instance;
 	struct lockdep_map		*nest_lock;
diff --git a/include/linux/sched.h b/include/linux/sched.h
index a10494a..c24348e 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1643,6 +1643,9 @@ struct task_struct {
 	unsigned int lockdep_recursion;
 	struct held_lock held_locks[MAX_LOCK_DEPTH];
 	gfp_t lockdep_reclaim_gfp;
+#ifdef CONFIG_LOCKED_ACCESS
+	u64 curr_acqchain_key;
+#endif
 #endif
 #ifdef CONFIG_UBSAN
 	unsigned int in_ubsan;
diff --git a/kernel/fork.c b/kernel/fork.c
index 2e391c7..d9fc51b 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -1404,6 +1404,9 @@ static struct task_struct *copy_process(unsigned long clone_flags,
 	p->lockdep_depth = 0; /* no locks held yet */
 	p->curr_chain_key = 0;
 	p->lockdep_recursion = 0;
+# ifdef CONFIG_LOCKED_ACCESS
+	p->curr_acqchain_key = 0;
+# endif
 #endif
 
 #ifdef CONFIG_DEBUG_MUTEXES
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 3aff961..77732a9 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3096,6 +3096,9 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	int chain_head = 0;
 	int class_idx;
 	u64 chain_key;
+#ifdef CONFIG_LOCKED_ACCESS
+	u64 acqchain_key;
+#endif
 
 	if (unlikely(!debug_locks))
 		return 0;
@@ -3203,6 +3206,9 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 		return 0;
 
 	chain_key = curr->curr_chain_key;
+#ifdef CONFIG_LOCKED_ACCESS
+	acqchain_key = curr->curr_acqchain_key;
+#endif
 	if (!depth) {
 		/*
 		 * How can we have a chain hash when we ain't got no keys?!
@@ -3213,12 +3219,23 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	}
 
 	hlock->prev_chain_key = chain_key;
+#ifdef CONFIG_LOCKED_ACCESS
+	hlock->prev_acqchain_key = acqchain_key;
+#endif
 	if (separate_irq_context(curr, hlock)) {
 		chain_key = 0;
+
+#ifdef CONFIG_LOCKED_ACCESS
+		acqchain_key = 0;
+#endif
+
 		chain_head = 1;
 	}
 	chain_key = iterate_chain_key(chain_key, id);
 
+#ifdef CONFIG_LOCKED_ACCESS
+	acqchain_key = iterate_acqchain_key(acqchain_key, ip);
+#endif
 	if (nest_lock && !__lock_is_held(nest_lock))
 		return print_lock_nested_lock_not_held(curr, hlock, ip);
 
@@ -3226,6 +3243,9 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 		return 0;
 
 	curr->curr_chain_key = chain_key;
+#ifdef CONFIG_LOCKED_ACCESS
+	curr->curr_acqchain_key = acqchain_key;
+#endif
 	curr->lockdep_depth++;
 	check_chain_key(curr);
 #ifdef CONFIG_DEBUG_LOCKDEP
@@ -3355,6 +3375,9 @@ found_it:
 
 	curr->lockdep_depth = i;
 	curr->curr_chain_key = hlock->prev_chain_key;
+#ifdef CONFIG_LOCKED_ACCESS
+	curr->curr_acqchain_key = hlock->prev_acqchain_key;
+#endif
 
 	for (; i < depth; i++) {
 		hlock = curr->held_locks + i;
@@ -3445,6 +3468,9 @@ found_it:
 
 	curr->lockdep_depth = i;
 	curr->curr_chain_key = hlock->prev_chain_key;
+#ifdef CONFIG_LOCKED_ACCESS
+	curr->curr_acqchain_key = hlock->prev_acqchain_key;
+#endif
 
 	for (i++; i < depth; i++) {
 		hlock = curr->held_locks + i;
@@ -3886,6 +3912,11 @@ void lockdep_reset(void)
 
 	raw_local_irq_save(flags);
 	current->curr_chain_key = 0;
+
+#ifdef CONFIG_LOCKED_ACCESS
+	current->curr_acqchain_key = 0;
+#endif
+
 	current->lockdep_depth = 0;
 	current->lockdep_recursion = 0;
 	memset(current->held_locks, 0, MAX_LOCK_DEPTH*sizeof(struct held_lock));
-- 
2.7.0

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

#1325669 — [RFC 4/6] lockdep: LOCKED_ACCESS: Introduce locked_access_point()

locked_access_point() is the entry point of the whole LOCKED_ACCESS
framework, every time a locked_access_point() is called, LOCKE_ACCESS
will correlate the data access location with the current acqchain.

So putting locked_access_point() at the data accesses you care about is
the step #2 to use LOCKED_ACCESS.

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 include/linux/lockdep.h  |  29 ++++++++++++
 kernel/locking/lockdep.c | 121 +++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 150 insertions(+)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 2ffe6c3..cf7b6c8 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -570,4 +570,33 @@ lockdep_rcu_suspicious(const char *file, const int line, const char *s)
 }
 #endif
 
+#ifdef CONFIG_LOCKED_ACCESS
+struct locked_access_location {
+	/* Filename of the access */
+	const char			*filename;
+	/* Line number of the access */
+	long				lineno;
+};
+
+#define LOCKED_ACCESS_TYPE_READ		1 /* read */
+
+extern void locked_access(struct locked_access_class *laclass,
+			  struct locked_access_location *access,
+			  int type);
+
+/*
+ * Entry point of LOCKED_ACCESS, should be called at every place the data
+ * accesses of the laclass happen.
+ *
+ * @_type must be one of the LOCKED_ACCESS_TYPE_*
+ */
+#define locked_access_point(_laclass, _type) \
+({ \
+	static struct locked_access_location a = { \
+				.filename = __FILE__, \
+				.lineno = __LINE__, \
+	}; \
+	locked_access(_laclass, &a, _type); \
+})
+#endif /* CONFIG_LOCKED_ACCESS */
 #endif /* __LINUX_LOCKDEP_H */
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 77732a9..996c2d5 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4503,4 +4503,125 @@ lookup_or_add_acqchain(struct locked_access_class *laclass,
 	return acqchain;
 }
 
+/*
+ * Lookup the data access at @loc in the ->accesses list of @acqchain.
+ *
+ * Must be called after @laclass is initialized.
+ */
+static int lookup_locked_access(struct acqchain *acqchain,
+				struct locked_access_location *loc)
+{
+	struct locked_access_struct *s;
+
+	list_for_each_entry_lockless(s, &acqchain->accesses, list) {
+		if (s->loc == loc)
+			return 1;
+	}
+	return 0;
+
+}
+
+/*
+ * Add the data access at @loc into the ->accesses list of @acqchain.
+ *
+ * Return 1 if one access is added, otherwise return 0.
+ *
+ * Must be called after @laclass is initialized.
+ */
+static int add_locked_access(struct locked_access_class *laclass,
+			     struct acqchain *acqchain,
+			     struct locked_access_location *loc,
+			     int type)
+{
+	unsigned long flags;
+	struct locked_access_struct *s;
+
+	local_irq_save(flags);
+	arch_spin_lock(&laclass->lock);
+
+	/* Lookup again while holding the lock */
+	if (lookup_locked_access(acqchain, loc)) {
+		arch_spin_unlock(&laclass->lock);
+		local_irq_restore(flags);
+		return 1;
+	}
+
+	if (unlikely(laclass->nr_access_structs >= MAX_LOCKED_ACCESS_STRUCTS)) {
+		arch_spin_unlock(&laclass->lock);
+		local_irq_restore(flags);
+		return 0;
+	}
+
+	s = laclass->access_structs + laclass->nr_access_structs;
+	s->loc = loc;
+	s->type = type;
+	laclass->nr_access_structs++;
+
+	/*
+	 * Pair with the list_for_each_entry_lockless() in
+	 * lookup_locked_access()
+	 */
+	list_add_tail_rcu(&s->list, &acqchain->accesses);
+
+	arch_spin_unlock(&laclass->lock);
+	local_irq_restore(flags);
+	return 1;
+}
+
+/*
+ * Correlate the data access at @loc with @acqchain for @laclass
+ *
+ * Must be called after @laclass is initialized.
+ */
+static int correlate_locked_access(struct locked_access_class *laclass,
+				   struct acqchain *acqchain,
+				   struct locked_access_location *loc,
+				   int type)
+{
+	if (lookup_locked_access(acqchain, loc))
+		return 1;
+
+	return add_locked_access(laclass, acqchain, loc, type);
+}
+
+/*
+ * The implementation of entry point locked_access_point(), called when a data
+ * access belonging to @laclass happens.
+ */
+void locked_access(struct locked_access_class *laclass,
+		   struct locked_access_location *loc,
+		   int type)
+{
+	u64 acqchain_key = current->curr_acqchain_key;
+	struct acqchain *acqchain;
+
+	if (unlikely(!laclass))
+		return;
+
+	/*
+	 * Don't track for data access for lockdep itself, because we rely
+	 * on the ->held_locks lockdep maintains, and if ->lockdep_recursion is
+	 * not 0, the lock is not being maintained in ->held_locks.
+	 */
+	if (unlikely(current->lockdep_recursion))
+		return;
+
+	/* Data access outside a critical section */
+	if (current->lockdep_depth <= 0)
+		return;
+
+	/*
+	 * we only check whether laclass is initialized in locked_access,
+	 * because this is the entry point of LOCKED_ACCESS.
+	 */
+	if (unlikely(!smp_load_acquire(&laclass->initialized)))
+		locked_access_class_init(laclass);
+
+	acqchain = lookup_or_add_acqchain(laclass, current, acqchain_key);
+
+	if (acqchain)
+		correlate_locked_access(laclass, acqchain, loc, type);
+}
+EXPORT_SYMBOL(locked_access);
+
 #endif /* CONFIG_LOCKED_ACCESS */
-- 
2.7.0

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

#1325674 — [RFC 5/6] lockdep: LOCKED_ACCESS: Add proc interface for locked access class

Provide the proc filesystem interface for LOCKED_ACCESS, for a locked
access class whose name is <name>, there will be a file at
/proc/locked_access/<name> containing all the information the
LOCKED_ACCESS has collected so far.

Also add a macro to define a locked access class.

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 kernel/locking/lockdep_internals.h |  17 +++++
 kernel/locking/lockdep_proc.c      | 127 +++++++++++++++++++++++++++++++++++++
 2 files changed, 144 insertions(+)

diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index 5e2e133..cacf869 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -241,4 +241,21 @@ struct locked_access_class {
 		.nr_acqchain_hlocks = 0,\
 		.nr_access_structs = 0, \
 	}
+
+extern int create_laclass_proc(const char *name,
+			   struct locked_access_class *laclass);
+
+#define DEFINE_CREATE_LACLASS_PROC(name) \
+static int __init ___create_##name##_laclass_proc(void) \
+{ \
+	return create_laclass_proc(#name, &name##_laclass); \
+} \
+late_initcall(___create_##name##_laclass_proc)
+
+/* Define a Locked Access Class and create its proc file */
+#define DEFINE_LACLASS(name) \
+	struct locked_access_class name##_laclass = \
+			INIT_LOCKED_ACCESS_DATA(name); \
+	EXPORT_SYMBOL(name##_laclass); \
+	DEFINE_CREATE_LACLASS_PROC(name)
 #endif /* CONFIG_LOCKED_ACCESS */
diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c
index dbb61a3..a278d1b 100644
--- a/kernel/locking/lockdep_proc.c
+++ b/kernel/locking/lockdep_proc.c
@@ -673,6 +673,130 @@ static const struct file_operations proc_lock_stat_operations = {
 };
 #endif /* CONFIG_LOCK_STAT */
 
+#ifdef CONFIG_LOCKED_ACCESS
+#include <linux/slab.h>
+static struct proc_dir_entry *locked_access_dir;
+static int seq_laclass_show(struct seq_file *m, void *v)
+{
+	struct locked_access_class *laclass;
+	loff_t *pos = v;
+	struct acqchain *acqchain;
+	struct locked_access_struct *s;
+	struct locked_access_location *loc;
+	unsigned long acq_ip;
+	int i;
+
+	laclass = (struct locked_access_class *)m->private;
+
+	/* Pair with the smp_store_release() in add_acqchain() */
+	if (*pos >= smp_load_acquire(&laclass->nr_acqchains) || *pos < 0)
+		return SEQ_SKIP;
+
+	acqchain = laclass->acqchains + *pos;
+
+	seq_printf(m, "ACQCHAIN 0x%llx, %d locks, irq_context %x:\n",
+			acqchain->chain_key, acqchain->depth,
+			acqchain->irq_context);
+	for (i = 0; i < acqchain->depth; i++) {
+		acq_ip = laclass->acqchain_hlocks[acqchain->base + i];
+		seq_printf(m, "%*sLOCK at [<%p>] %pSR\n",
+				(i+1) * 2, "", (void *) acq_ip,
+				(void *) acq_ip);
+	}
+
+	/* Pair with the list_add_tail_rcu() in add_locked_access() */
+	list_for_each_entry_lockless(s, &acqchain->accesses, list) {
+		loc = s->loc;
+		seq_printf(m, "%*sACCESS TYPE %x at %s:%ld\n",
+				(i+1) * 2, "", s->type, loc->filename,
+				loc->lineno);
+
+	}
+	return 0;
+}
+
+static void *seq_laclass_start(struct seq_file *m, loff_t *pos)
+{
+	struct locked_access_class *laclass;
+	loff_t *rpos;
+
+	laclass = (struct locked_access_class *)m->private;
+
+	/* Pair with the smp_store_release() in add_acqchain() */
+	if (*pos >= smp_load_acquire(&laclass->nr_acqchains) || *pos < 0)
+		return NULL;
+
+	rpos = kzalloc(sizeof(loff_t), GFP_KERNEL);
+
+	if (!rpos)
+		return NULL;
+
+	*rpos = *pos;
+
+	return rpos;
+}
+
+static void *seq_laclass_next(struct seq_file *m, void *v, loff_t *pos)
+{
+	struct locked_access_class *laclass;
+	loff_t *rpos = v;
+
+	laclass = (struct locked_access_class *)m->private;
+
+	/* Pair with the smp_store_release() in add_acqchain() */
+	if (*pos + 1 < smp_load_acquire(&laclass->nr_acqchains) && *pos >= 0) {
+		*pos = ++*rpos;
+		return rpos;
+	}
+
+	return NULL;
+}
+
+static void seq_laclass_stop(struct seq_file *m, void *v)
+{
+	kfree(v);
+}
+
+static const struct seq_operations seq_laclass_ops = {
+	.start = seq_laclass_start,
+	.next = seq_laclass_next,
+	.stop = seq_laclass_stop,
+	.show = seq_laclass_show
+};
+
+static int proc_laclass_open(struct inode *inode, struct file *file)
+{
+	struct seq_file *seq;
+	int rc;
+
+	rc = seq_open(file, &seq_laclass_ops);
+
+	if (rc != 0)
+		return rc;
+
+	if (!PDE_DATA(inode))
+		return -ENOENT;
+
+	seq = file->private_data;
+	seq->private = PDE_DATA(inode);
+
+	return 0;
+}
+
+static const struct file_operations proc_laclass_operations = {
+	.open		= proc_laclass_open,
+	.read		= seq_read,
+	.llseek		= seq_lseek,
+	.release	= seq_release
+};
+
+int create_laclass_proc(const char *name, struct locked_access_class *laclass)
+{
+	return !proc_create_data(name, S_IRUSR, locked_access_dir,
+			&proc_laclass_operations, laclass);
+}
+#endif /* CONFIG_LOCKED_ACCESS */
+
 static int __init lockdep_proc_init(void)
 {
 	proc_create("lockdep", S_IRUSR, NULL, &proc_lockdep_operations);
@@ -688,6 +812,9 @@ static int __init lockdep_proc_init(void)
 		    &proc_lock_stat_operations);
 #endif
 
+#ifdef CONFIG_LOCKED_ACCESS
+	locked_access_dir = proc_mkdir("locked_access", NULL);
+#endif /* CONFIG_LOCKED_ACCESS */
 	return 0;
 }
 
-- 
2.7.0

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web