Now we have four kinds of dependencies in the dependency graph, and not all the pathes carry strong dependencies, for example:
Given lock A, B, C, if we have: CPU1 CPU2 ============= ============== write_lock(A); read_lock(B); read_lock(B); write_lock(C); then we have dependencies A--(NR)-->B, and B--(RN)-->C, (NR and RN are to indicate the dependency kind), A actually doesn't have strong dependency to C(IOW, C doesn't depend on A), to see this, let's say we have a third CPU3 doing: CPU3: ============= write_lock(C); write_lock(A); , this is not a deadlock. However if we change the read_lock() on CPU2 to a write_lock(), it's a deadlock then. So A --(NR)--> B --(RN)--> C is not a strong dependency path but A --(NR)--> B --(NN)-->C is a strong dependency path. We can generalize this as: If a path of dependencies doesn't have two adjacent dependencies as (*R)--L-->(R*), where L is some lock, it is a strong dependency path, otherwise it's not. Now our mission is to make __bfs() traverse only the strong dependency paths, which is simple: we record whether we have --(*R)--> at the current tail of the path in lock_list::is_rr, and whenever we pick a dependency in the traverse, we 1) make sure we don't pick a --(R*)--> dependency if our current tail is --(*R)--> and 2) greedily pick a --(*N)--> as hard as possible. With this extension for __bfs(), we now need to initialize the root of __bfs() properly(with a correct ->is_rr), to do so, we introduce some helper functions, which also cleans up a little bit for the __bfs() root initialization code. Signed-off-by: Boqun Feng <boqun.f...@gmail.com> --- include/linux/lockdep.h | 2 ++ kernel/locking/lockdep.c | 81 ++++++++++++++++++++++++++++++++++++++---------- 2 files changed, 66 insertions(+), 17 deletions(-) diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h index 35b3fc0d6793..68cbe7e8399a 100644 --- a/include/linux/lockdep.h +++ b/include/linux/lockdep.h @@ -194,6 +194,8 @@ struct lock_list { int distance; /* bitmap of different dependencies from head to this */ u16 dep; + /* used by BFS to record whether this is picked as a recursive read */ + u16 is_rr; /* * The parent field is used to implement breadth-first search, and the diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index 3bc69848fe08..9e7647e40918 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -1052,6 +1052,54 @@ static inline unsigned int calc_dep(int prev, int next) return 1U << __calc_dep_bit(prev, next); } +/* + * return -1 if no proper dependency could be picked + * return 0 if a * --> N dependency could be picked + * return 1 if only a * --> R dependency could be picked + * + * N: non-recursive lock + * R: recursive read lock + */ +static inline int pick_dep(u16 is_rr, u16 cap_dep) +{ + if (is_rr) { /* could only pick N --> */ + if (cap_dep & DEP_NN_MASK) + return 0; + else if (cap_dep & DEP_NR_MASK) + return 1; + else + return -1; + } else { + if (cap_dep & DEP_NN_MASK || cap_dep & DEP_RN_MASK) + return 0; + else + return 1; + } +} + +/* + * Initialize a lock_list entry @lock belonging to @class as the root for a BFS + * search. + */ +static inline void __bfs_init_root(struct lock_list *lock, + struct lock_class *class) +{ + lock->class = class; + lock->parent = NULL; + lock->is_rr = 0; +} + +/* + * Initialize a lock_list entry @lock based on a lock acquisition @hlock as the + * root for a BFS search. + */ +static inline void bfs_init_root(struct lock_list *lock, + struct held_lock *hlock) +{ + __bfs_init_root(lock, hlock_class(hlock)); + lock->is_rr = (hlock->read == 2); +} + static enum bfs_result __bfs(struct lock_list *source_entry, void *data, int (*match)(struct lock_list *entry, void *data), @@ -1062,6 +1110,7 @@ static enum bfs_result __bfs(struct lock_list *source_entry, struct list_head *head; struct circular_queue *cq = &lock_cq; enum bfs_result ret = BFS_RNOMATCH; + int is_rr, next_is_rr; if (match(source_entry, data)) { *target_entry = source_entry; @@ -1107,11 +1156,18 @@ static enum bfs_result __bfs(struct lock_list *source_entry, else head = &lock->class->locks_before; + is_rr = lock->is_rr; + DEBUG_LOCKS_WARN_ON(!irqs_disabled()); list_for_each_entry_rcu(entry, head, entry) { unsigned int cq_depth; + next_is_rr = pick_dep(is_rr, entry->dep); + if (next_is_rr < 0) + continue; + entry->is_rr = next_is_rr; + visit_lock_entry(entry, lock); if (match(entry, data)) { *target_entry = entry; @@ -1362,8 +1418,7 @@ unsigned long lockdep_count_forward_deps(struct lock_class *class) unsigned long ret, flags; struct lock_list this; - this.parent = NULL; - this.class = class; + __bfs_init_root(&this, class); local_irq_save(flags); arch_spin_lock(&lockdep_lock); @@ -1389,8 +1444,7 @@ unsigned long lockdep_count_backward_deps(struct lock_class *class) unsigned long ret, flags; struct lock_list this; - this.parent = NULL; - this.class = class; + __bfs_init_root(&this, class); local_irq_save(flags); arch_spin_lock(&lockdep_lock); @@ -1677,17 +1731,14 @@ check_usage(struct task_struct *curr, struct held_lock *prev, struct lock_list *uninitialized_var(target_entry); struct lock_list *uninitialized_var(target_entry1); - this.parent = NULL; - - this.class = hlock_class(prev); + bfs_init_root(&this, prev); ret = find_usage_backwards(&this, bit_backwards, &target_entry); if (bfs_error(ret)) return print_bfs_bug(ret); if (ret == BFS_RNOMATCH) return 1; - that.parent = NULL; - that.class = hlock_class(next); + bfs_init_root(&that, next); ret = find_usage_forwards(&that, bit_forwards, &target_entry1); if (bfs_error(ret)) return print_bfs_bug(ret); @@ -1946,8 +1997,7 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev, * We are using global variables to control the recursion, to * keep the stackframe size of the recursive functions low: */ - this.class = hlock_class(next); - this.parent = NULL; + bfs_init_root(&this, next); ret = check_noncircular(&this, hlock_class(prev), &target_entry); if (unlikely(ret == BFS_RMATCH)) return print_circular_bug(&this, target_entry, next, prev, trace); @@ -1996,8 +2046,7 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev, /* * Is the <prev> -> <next> link redundant? */ - this.class = hlock_class(prev); - this.parent = NULL; + bfs_init_root(&this, prev); ret = check_redundant(&this, hlock_class(next), &target_entry); if (ret == BFS_RMATCH) { debug_atomic_inc(nr_redundant); @@ -2762,8 +2811,7 @@ check_usage_forwards(struct task_struct *curr, struct held_lock *this, struct lock_list root; struct lock_list *uninitialized_var(target_entry); - root.parent = NULL; - root.class = hlock_class(this); + bfs_init_root(&root, this); ret = find_usage_forwards(&root, bit, &target_entry); if (bfs_error(ret)) return print_bfs_bug(ret); @@ -2786,8 +2834,7 @@ check_usage_backwards(struct task_struct *curr, struct held_lock *this, struct lock_list root; struct lock_list *uninitialized_var(target_entry); - root.parent = NULL; - root.class = hlock_class(this); + bfs_init_root(&root, this); ret = find_usage_backwards(&root, bit, &target_entry); if (bfs_error(ret)) return print_bfs_bug(ret); -- 2.14.1