lockdep: Implement lockdep_count_*ward_deps by BFS

Implement lockdep_count_{for,back}ward using BFS.

Signed-off-by: Ming Lei <tom.leiming@gmail.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
LKML-Reference: <1246201486-7308-8-git-send-email-tom.leiming@gmail.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>

1 files changed, 25 insertions, 27 deletions

diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index 938dc500f1aa..b896f23e00cf 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -1115,61 +1115,59 @@ static noinline int print_bfs_bug(int ret)
         return 0;
 }
 
-unsigned long __lockdep_count_forward_deps(struct lock_class *class,
-                                           unsigned int depth)
+static int noop_count(struct lock_list *entry, void *data)
 {
-        struct lock_list *entry;
-        unsigned long ret = 1;
+        (*(unsigned long *)data)++;
+        return 0;
+}
 
-        if (lockdep_dependency_visit(class, depth))
-                return 0;
+unsigned long __lockdep_count_forward_deps(struct lock_list *this)
+{
+        unsigned long  count = 0;
+        struct lock_list *uninitialized_var(target_entry);
 
-        /*
-         * Recurse this class's dependency list:
-         */
-        list_for_each_entry(entry, &class->locks_after, entry)
-                ret += __lockdep_count_forward_deps(entry->class, depth + 1);
+        __bfs_forwards(this, (void *)&count, noop_count, &target_entry);
 
-        return ret;
+        return count;
 }
-
 unsigned long lockdep_count_forward_deps(struct lock_class *class)
 {
         unsigned long ret, flags;
+        struct lock_list this;
+
+        this.parent = NULL;
+        this.class = class;
 
         local_irq_save(flags);
         __raw_spin_lock(&lockdep_lock);
-        ret = __lockdep_count_forward_deps(class, 0);
+        ret = __lockdep_count_forward_deps(&this);
         __raw_spin_unlock(&lockdep_lock);
         local_irq_restore(flags);
 
         return ret;
 }
 
-unsigned long __lockdep_count_backward_deps(struct lock_class *class,
-                                            unsigned int depth)
+unsigned long __lockdep_count_backward_deps(struct lock_list *this)
 {
-        struct lock_list *entry;
-        unsigned long ret = 1;
+        unsigned long  count = 0;
+        struct lock_list *uninitialized_var(target_entry);
 
-        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);
+        __bfs_backwards(this, (void *)&count, noop_count, &target_entry);
 
-        return ret;
+        return count;
 }
 
 unsigned long lockdep_count_backward_deps(struct lock_class *class)
 {
         unsigned long ret, flags;
+        struct lock_list this;
+
+        this.parent = NULL;
+        this.class = class;
 
         local_irq_save(flags);
         __raw_spin_lock(&lockdep_lock);
-        ret = __lockdep_count_backward_deps(class, 0);
+        ret = __lockdep_count_backward_deps(&this);
         __raw_spin_unlock(&lockdep_lock);
         local_irq_restore(flags);