From: David Miller <[email protected]>
When we traverse the graph, either forwards or backwards, we
are interested in whether a certain property exists somewhere
in a node reachable in the graph.
Therefore it is never necessary to traverse through a node more
than once to get a correct answer to the given query.
Take advantage of this property using a global ID counter so that we
need not clear all the markers in all the lock_class entries before
doing a traversal. A new ID is choosen when we start to traverse, and
we continue through a lock_class only if it's ID hasn't been marked
with the new value yet.
This short-circuiting is essential especially for high CPU count
systems. The scheduler has a runqueue per cpu, and needs to take
two runqueue locks at a time, which leads to long chains of
backwards and forwards subgraphs from these runqueue lock nodes.
Without the short-circuit implemented here, a graph traversal on
a runqueue lock can take up to (1 << (N - 1)) checks on a system
with N cpus.
For anything more than 16 cpus or so, lockdep will eventually bring
the machine to a complete standstill.
Signed-off-by: David S. Miller <[email protected]>
Signed-off-by: Peter Zijlstra <[email protected]>
---
include/linux/lockdep.h | 1
kernel/lockdep.c | 86 +++++++++++++++++++++++++++++++++++++++++++++
kernel/lockdep_internals.h | 3 +
kernel/lockdep_proc.c | 34 +----------------
4 files changed, 93 insertions(+), 31 deletions(-)
Index: linux-2.6/include/linux/lockdep.h
===================================================================
--- linux-2.6.orig/include/linux/lockdep.h
+++ linux-2.6/include/linux/lockdep.h
@@ -89,6 +89,7 @@ struct lock_class {
struct lockdep_subclass_key *key;
unsigned int subclass;
+ unsigned int dep_gen_id;
/*
* IRQ/softirq usage tracking bits:
Index: linux-2.6/kernel/lockdep.c
===================================================================
--- linux-2.6.orig/kernel/lockdep.c
+++ linux-2.6/kernel/lockdep.c
@@ -372,6 +372,19 @@ unsigned int nr_process_chains;
unsigned int max_lockdep_depth;
unsigned int max_recursion_depth;
+static unsigned int lockdep_dependency_gen_id;
+
+static bool lockdep_dependency_visit(struct lock_class *source,
+ unsigned int depth)
+{
+ if (!depth)
+ lockdep_dependency_gen_id++;
+ if (source->dep_gen_id == lockdep_dependency_gen_id)
+ return true;
+ source->dep_gen_id = lockdep_dependency_gen_id;
+ return false;
+}
+
#ifdef CONFIG_DEBUG_LOCKDEP
/*
* We cannot printk in early bootup code. Not even early_printk()
@@ -558,6 +571,9 @@ static void print_lock_dependencies(stru
{
struct lock_list *entry;
+ if (lockdep_dependency_visit(class, depth))
+ return;
+
if (DEBUG_LOCKS_WARN_ON(depth >= 20))
return;
@@ -959,6 +975,67 @@ static int noinline print_infinite_recur
return 0;
}
+unsigned long __lockdep_count_forward_deps(struct lock_class *class,
+ unsigned int depth)
+{
+ struct lock_list *entry;
+ unsigned long ret = 1;
+
+ if (lockdep_dependency_visit(class, depth))
+ return 0;
+
+ /*
+ * Recurse this class's dependency list:
+ */
+ list_for_each_entry(entry, &class->locks_after, entry)
+ ret += __lockdep_count_forward_deps(entry->class, depth + 1);
+
+ return ret;
+}
+
+unsigned long lockdep_count_forward_deps(struct lock_class *class)
+{
+ unsigned long ret, flags;
+
+ local_irq_save(flags);
+ __raw_spin_lock(&lockdep_lock);
+ ret = __lockdep_count_forward_deps(class, 0);
+ __raw_spin_unlock(&lockdep_lock);
+ local_irq_restore(flags);
+
+ return ret;
+}
+
+unsigned long __lockdep_count_backward_deps(struct lock_class *class,
+ unsigned int depth)
+{
+ struct lock_list *entry;
+ unsigned long ret = 1;
+
+ if (lockdep_dependency_visit(class, depth))
+ return 0;
+ /*
+ * Recurse this class's dependency list:
+ */
+ list_for_each_entry(entry, &class->locks_before, entry)
+ ret += __lockdep_count_backward_deps(entry->class, depth + 1);
+
+ return ret;
+}
+
+unsigned long lockdep_count_backward_deps(struct lock_class *class)
+{
+ unsigned long ret, flags;
+
+ local_irq_save(flags);
+ __raw_spin_lock(&lockdep_lock);
+ ret = __lockdep_count_backward_deps(class, 0);
+ __raw_spin_unlock(&lockdep_lock);
+ local_irq_restore(flags);
+
+ return ret;
+}
+
/*
* Prove that the dependency graph starting at <entry> can not
* lead to <target>. Print an error and return 0 if it does.
@@ -968,6 +1045,9 @@ check_noncircular(struct lock_class *sou
{
struct lock_list *entry;
+ if (lockdep_dependency_visit(source, depth))
+ return 1;
+
debug_atomic_inc(&nr_cyclic_check_recursions);
if (depth > max_recursion_depth)
max_recursion_depth = depth;
@@ -1011,6 +1091,9 @@ find_usage_forwards(struct lock_class *s
struct lock_list *entry;
int ret;
+ if (lockdep_dependency_visit(source, depth))
+ return 1;
+
if (depth > max_recursion_depth)
max_recursion_depth = depth;
if (depth >= RECURSION_LIMIT)
@@ -1050,6 +1133,9 @@ find_usage_backwards(struct lock_class *
struct lock_list *entry;
int ret;
+ if (lockdep_dependency_visit(source, depth))
+ return 1;
+
if (!__raw_spin_is_locked(&lockdep_lock))
return DEBUG_LOCKS_WARN_ON(1);
Index: linux-2.6/kernel/lockdep_internals.h
===================================================================
--- linux-2.6.orig/kernel/lockdep_internals.h
+++ linux-2.6/kernel/lockdep_internals.h
@@ -53,6 +53,9 @@ extern unsigned int nr_process_chains;
extern unsigned int max_lockdep_depth;
extern unsigned int max_recursion_depth;
+extern unsigned long lockdep_count_forward_deps(struct lock_class *);
+extern unsigned long lockdep_count_backward_deps(struct lock_class *);
+
#ifdef CONFIG_DEBUG_LOCKDEP
/*
* Various lockdep statistics:
Index: linux-2.6/kernel/lockdep_proc.c
===================================================================
--- linux-2.6.orig/kernel/lockdep_proc.c
+++ linux-2.6/kernel/lockdep_proc.c
@@ -63,34 +63,6 @@ static void l_stop(struct seq_file *m, v
{
}
-static unsigned long count_forward_deps(struct lock_class *class)
-{
- struct lock_list *entry;
- unsigned long ret = 1;
-
- /*
- * Recurse this class's dependency list:
- */
- list_for_each_entry(entry, &class->locks_after, entry)
- ret += count_forward_deps(entry->class);
-
- return ret;
-}
-
-static unsigned long count_backward_deps(struct lock_class *class)
-{
- struct lock_list *entry;
- unsigned long ret = 1;
-
- /*
- * Recurse this class's dependency list:
- */
- list_for_each_entry(entry, &class->locks_before, entry)
- ret += count_backward_deps(entry->class);
-
- return ret;
-}
-
static void print_name(struct seq_file *m, struct lock_class *class)
{
char str[128];
@@ -124,10 +96,10 @@ static int l_show(struct seq_file *m, vo
#ifdef CONFIG_DEBUG_LOCKDEP
seq_printf(m, " OPS:%8ld", class->ops);
#endif
- nr_forward_deps = count_forward_deps(class);
+ nr_forward_deps = lockdep_count_forward_deps(class);
seq_printf(m, " FD:%5ld", nr_forward_deps);
- nr_backward_deps = count_backward_deps(class);
+ nr_backward_deps = lockdep_count_backward_deps(class);
seq_printf(m, " BD:%5ld", nr_backward_deps);
get_usage_chars(class, &c1, &c2, &c3, &c4);
@@ -350,7 +322,7 @@ static int lockdep_stats_show(struct seq
if (class->usage_mask & LOCKF_ENABLED_HARDIRQS_READ)
nr_hardirq_read_unsafe++;
- sum_forward_deps += count_forward_deps(class);
+ sum_forward_deps += lockdep_count_forward_deps(class);
}
#ifdef CONFIG_DEBUG_LOCKDEP
DEBUG_LOCKS_WARN_ON(debug_atomic_read(&nr_unused_locks) != nr_unused);
--
From: Peter Zijlstra <[email protected]>
Date: Mon, 04 Aug 2008 15:03:18 +0200
> When we traverse the graph, either forwards or backwards, we
> are interested in whether a certain property exists somewhere
> in a node reachable in the graph.
...
> Signed-off-by: David S. Miller <[email protected]>
> Signed-off-by: Peter Zijlstra <[email protected]>
Peter, when Ingo added this to his tree he needed to add a build
fix of some sort. Did you include that here?
I think the problem was that if CONFIG_PROVE_LOCKING is not
set, we need to add nop inline versions of lockdep_count_*_deps()
in kernel/lockdep_internals.h
See:
http://marc.info/?l=linux-kernel&m=121758260130275&w=2
On Tue, 2008-08-05 at 01:34 -0700, David Miller wrote:
> From: Peter Zijlstra <[email protected]>
> Date: Mon, 04 Aug 2008 15:03:18 +0200
>
> > When we traverse the graph, either forwards or backwards, we
> > are interested in whether a certain property exists somewhere
> > in a node reachable in the graph.
> ...
> > Signed-off-by: David S. Miller <[email protected]>
> > Signed-off-by: Peter Zijlstra <[email protected]>
>
> Peter, when Ingo added this to his tree he needed to add a build
> fix of some sort. Did you include that here?
>
> I think the problem was that if CONFIG_PROVE_LOCKING is not
> set, we need to add nop inline versions of lockdep_count_*_deps()
> in kernel/lockdep_internals.h
>
> See:
>
> http://marc.info/?l=linux-kernel&m=121758260130275&w=2
Probably missed that, thanks for reminding me.
Andrew, please pick up:
---
From: Ingo Molnar <[email protected]>
Date: Fri, 1 Aug 2008 11:23:50 +0200
Subject: [PATCH] lockdep: build fix
fix:
kernel/built-in.o: In function `lockdep_stats_show':
lockdep_proc.c:(.text+0x3cb2f): undefined reference to `lockdep_count_forward_deps'
kernel/built-in.o: In function `l_show':
lockdep_proc.c:(.text+0x3d02b): undefined reference to `lockdep_count_forward_deps'
lockdep_proc.c:(.text+0x3d047): undefined reference to `lockdep_count_backward_deps'
Signed-off-by: Ingo Molnar <[email protected]>
---
kernel/lockdep_internals.h | 13 +++++++++++++
1 files changed, 13 insertions(+), 0 deletions(-)
diff --git a/kernel/lockdep_internals.h b/kernel/lockdep_internals.h
index 68d44ec..f5c6a14 100644
--- a/kernel/lockdep_internals.h
+++ b/kernel/lockdep_internals.h
@@ -53,8 +53,21 @@ extern unsigned int nr_process_chains;
extern unsigned int max_lockdep_depth;
extern unsigned int max_recursion_depth;
+#ifdef CONFIG_PROVE_LOCKING
extern unsigned long lockdep_count_forward_deps(struct lock_class *);
extern unsigned long lockdep_count_backward_deps(struct lock_class *);
+#else
+static inline unsigned long
+lockdep_count_forward_deps(struct lock_class *class)
+{
+ return 0;
+}
+static inline unsigned long
+lockdep_count_backward_deps(struct lock_class *class)
+{
+ return 0;
+}
+#endif
#ifdef CONFIG_DEBUG_LOCKDEP
/*
On Tue, Aug 5, 2008 at 1:46 AM, Peter Zijlstra <[email protected]> wrote:
> On Tue, 2008-08-05 at 01:34 -0700, David Miller wrote:
>> See:
>>
>> http://marc.info/?l=linux-kernel&m=121758260130275&w=2
>
> Probably missed that, thanks for reminding me.
>
> Andrew, please pick up:
>
> ---
> From: Ingo Molnar <[email protected]>
> Date: Fri, 1 Aug 2008 11:23:50 +0200
> Subject: [PATCH] lockdep: build fix
>
> fix:
>
> kernel/built-in.o: In function `lockdep_stats_show':
> lockdep_proc.c:(.text+0x3cb2f): undefined reference to `lockdep_count_forward_deps'
> kernel/built-in.o: In function `l_show':
> lockdep_proc.c:(.text+0x3d02b): undefined reference to `lockdep_count_forward_deps'
> lockdep_proc.c:(.text+0x3d047): undefined reference to `lockdep_count_backward_deps'
>
> Signed-off-by: Ingo Molnar <[email protected]>
> ---
> kernel/lockdep_internals.h | 13 +++++++++++++
> 1 files changed, 13 insertions(+), 0 deletions(-)
>
> diff --git a/kernel/lockdep_internals.h b/kernel/lockdep_internals.h
> index 68d44ec..f5c6a14 100644
> --- a/kernel/lockdep_internals.h
> +++ b/kernel/lockdep_internals.h
> @@ -53,8 +53,21 @@ extern unsigned int nr_process_chains;
> extern unsigned int max_lockdep_depth;
> extern unsigned int max_recursion_depth;
>
> +#ifdef CONFIG_PROVE_LOCKING
> extern unsigned long lockdep_count_forward_deps(struct lock_class *);
> extern unsigned long lockdep_count_backward_deps(struct lock_class *);
> +#else
> +static inline unsigned long
> +lockdep_count_forward_deps(struct lock_class *class)
> +{
> + return 0;
> +}
> +static inline unsigned long
> +lockdep_count_backward_deps(struct lock_class *class)
> +{
> + return 0;
> +}
> +#endif
>
> #ifdef CONFIG_DEBUG_LOCKDEP
> /*
>
>
Looks like this is needed for 2.6.27-rc3 to build here. Also noted,
regardless of the patch:
kernel/lockdep.c:580: warning: 'print_lock_dependencies' defined but not used
Tim
* Tim Pepper <[email protected]> wrote:
> On Tue, Aug 5, 2008 at 1:46 AM, Peter Zijlstra <[email protected]> wrote:
> > On Tue, 2008-08-05 at 01:34 -0700, David Miller wrote:
> >> See:
> >>
> >> http://marc.info/?l=linux-kernel&m=121758260130275&w=2
> >
> > Probably missed that, thanks for reminding me.
> >
> > Andrew, please pick up:
> >
> > ---
> > From: Ingo Molnar <[email protected]>
> > Date: Fri, 1 Aug 2008 11:23:50 +0200
> > Subject: [PATCH] lockdep: build fix
> >
> > fix:
> >
> > kernel/built-in.o: In function `lockdep_stats_show':
> > lockdep_proc.c:(.text+0x3cb2f): undefined reference to `lockdep_count_forward_deps'
> > kernel/built-in.o: In function `l_show':
> > lockdep_proc.c:(.text+0x3d02b): undefined reference to `lockdep_count_forward_deps'
> > lockdep_proc.c:(.text+0x3d047): undefined reference to `lockdep_count_backward_deps'
> >
> > Signed-off-by: Ingo Molnar <[email protected]>
> > ---
> > kernel/lockdep_internals.h | 13 +++++++++++++
> > 1 files changed, 13 insertions(+), 0 deletions(-)
> >
> > diff --git a/kernel/lockdep_internals.h b/kernel/lockdep_internals.h
> > index 68d44ec..f5c6a14 100644
> > --- a/kernel/lockdep_internals.h
> > +++ b/kernel/lockdep_internals.h
> > @@ -53,8 +53,21 @@ extern unsigned int nr_process_chains;
> > extern unsigned int max_lockdep_depth;
> > extern unsigned int max_recursion_depth;
> >
> > +#ifdef CONFIG_PROVE_LOCKING
> > extern unsigned long lockdep_count_forward_deps(struct lock_class *);
> > extern unsigned long lockdep_count_backward_deps(struct lock_class *);
> > +#else
> > +static inline unsigned long
> > +lockdep_count_forward_deps(struct lock_class *class)
> > +{
> > + return 0;
> > +}
> > +static inline unsigned long
> > +lockdep_count_backward_deps(struct lock_class *class)
> > +{
> > + return 0;
> > +}
> > +#endif
> >
> > #ifdef CONFIG_DEBUG_LOCKDEP
> > /*
> >
> >
>
>
> Looks like this is needed for 2.6.27-rc3 to build here. [...]
ok, i've put this into tip/core/urgent, i mistakenly applied it to
tip/master so it didnt go to Linus in time. Below is the commit from
tip/core/urgent.
Ingo
----------------->
>From d6672c501852d577097f6757c311d937aca0b04b Mon Sep 17 00:00:00 2001
From: Ingo Molnar <[email protected]>
Date: Fri, 1 Aug 2008 11:23:50 +0200
Subject: [PATCH] lockdep: build fix
fix:
kernel/built-in.o: In function `lockdep_stats_show':
lockdep_proc.c:(.text+0x3cb2f): undefined reference to `lockdep_count_forward_deps'
kernel/built-in.o: In function `l_show':
lockdep_proc.c:(.text+0x3d02b): undefined reference to `lockdep_count_forward_deps'
lockdep_proc.c:(.text+0x3d047): undefined reference to `lockdep_count_backward_deps'
Signed-off-by: Ingo Molnar <[email protected]>
---
kernel/lockdep_internals.h | 13 +++++++++++++
1 files changed, 13 insertions(+), 0 deletions(-)
diff --git a/kernel/lockdep_internals.h b/kernel/lockdep_internals.h
index 55db193..56b1969 100644
--- a/kernel/lockdep_internals.h
+++ b/kernel/lockdep_internals.h
@@ -50,8 +50,21 @@ extern unsigned int nr_process_chains;
extern unsigned int max_lockdep_depth;
extern unsigned int max_recursion_depth;
+#ifdef CONFIG_PROVE_LOCKING
extern unsigned long lockdep_count_forward_deps(struct lock_class *);
extern unsigned long lockdep_count_backward_deps(struct lock_class *);
+#else
+static inline unsigned long
+lockdep_count_forward_deps(struct lock_class *class)
+{
+ return 0;
+}
+static inline unsigned long
+lockdep_count_backward_deps(struct lock_class *class)
+{
+ return 0;
+}
+#endif
#ifdef CONFIG_DEBUG_LOCKDEP
/*