| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Mon, 28 Aug 2017 22:56:56 +0800
From: Boqun Feng <boqun.feng@...il.com>
To: linux-kernel@...r.kernel.org
Cc: Ingo Molnar <mingo@...hat.com>,
Peter Zijlstra <peterz@...radead.org>,
Gautham R Shenoy <ego@...ibm.com>,
Byungchul Park <byungchul.park@....com>,
Boqun Feng <boqun.feng@...il.com>
Subject: [RFC tip 4/5] lockdep: Support deadlock detection for recursive read locks in check_noncircular()
Currently, lockdep only has limit support for deadlock detection for
recursive read locks.
The basic idea of the detection is:
Firstly we add recursive read lock into the graph, so now we have four
types of dependency: 1) non-recursive to recursive(NR), 2) non-recursive
to non-recursive(NN), 3) recursive to non-recursive(RN) and 4) recursive
to recursive(RR).
And further in __bfs() we now allow switch the lock read/write status in
the traverse, in other words, if the __bfs() went from A to B through
write_lock(A) --> read_lock(B), we would allow __bfs() to go from B to C
through write_lock(B) --> read_lock(C).
However, we limit the traverse reflect the real dependencies, and the
rule is simple: the bfs traverse can go through A to B and then to C iff
we can find dependency A --> B and B --> C where B is not a recursive
read lock in at least one of dependencies(A --> B and B-->C). In other
words, a lock cannot be the transfer station if it only has *->R
dependencies with previous locks and R->* dependencies with following
locks.
If we could still find a circle under this rule, a deadlock is reported.
Signed-off-by: Boqun Feng <boqun.feng@...il.com>
---
include/linux/lockdep.h | 4 +++
kernel/locking/lockdep.c | 93 +++++++++++++++++++++++++++++++++++++++---------
2 files changed, 81 insertions(+), 16 deletions(-)
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 78bb7133abed..bf75338879f5 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -192,6 +192,10 @@ struct lock_list {
struct lock_class *class;
struct stack_trace trace;
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 535f6ec1a393..245324c59706 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -871,7 +871,7 @@ static struct lock_list *alloc_list_entry(void)
* Add a new dependency to the head of the list:
*/
static int add_lock_to_list(struct lock_class *this, struct list_head *head,
- unsigned long ip, int distance,
+ unsigned long ip, int distance, unsigned int dep,
struct stack_trace *trace)
{
struct lock_list *entry;
@@ -884,6 +884,7 @@ static int add_lock_to_list(struct lock_class *this, struct list_head *head,
return 0;
entry->class = this;
+ entry->dep = dep;
entry->distance = distance;
entry->trace = *trace;
/*
@@ -1028,6 +1029,58 @@ static inline bool bfs_error(enum bfs_result res)
return res < 0;
}
+#define DEP_NN_BIT 0
+#define DEP_RN_BIT 1
+#define DEP_NR_BIT 2
+#define DEP_RR_BIT 3
+
+#define DEP_NN_MASK (1U << (DEP_NN_BIT))
+#define DEP_RN_MASK (1U << (DEP_RN_BIT))
+#define DEP_NR_MASK (1U << (DEP_NR_BIT))
+#define DEP_RR_MASK (1U << (DEP_RR_BIT))
+
+static inline unsigned int __calc_dep_bit(int prev, int next)
+{
+ if (prev == 2 && next != 2)
+ return DEP_RN_BIT;
+ if (prev != 2 && next == 2)
+ return DEP_NR_BIT;
+ if (prev == 2 && next == 2)
+ return DEP_RR_BIT;
+ else
+ return DEP_NN_BIT;
+}
+
+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;
+ }
+}
+
static enum bfs_result __bfs(struct lock_list *source_entry,
void *data,
int (*match)(struct lock_list *entry, void *data),
@@ -1038,6 +1091,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;
@@ -1071,11 +1125,20 @@ 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) {
if (!lock_accessed(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;
mark_lock_accessed(entry, lock);
if (match(entry, data)) {
*target_entry = entry;
@@ -1367,7 +1430,7 @@ unsigned long lockdep_count_backward_deps(struct lock_class *class)
}
/*
- * Prove that the dependency graph starting at <entry> can not
+ * Prove that the dependency graph starting at <root> can not
* lead to <target>. Print an error and return BFS_RMATCH if it does.
*/
static noinline enum bfs_result
@@ -1913,8 +1976,10 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
*/
this.class = hlock_class(next);
this.parent = NULL;
+ this.is_rr = (next->read == 2);
ret = check_noncircular(&this, hlock_class(prev), &target_entry);
- if (unlikely(ret == BFS_RMATCH))
+ if (unlikely(ret == BFS_RMATCH) &&
+ (prev->read != 2 || !target_entry->is_rr))
return print_circular_bug(&this, target_entry, next, prev, trace);
else if (unlikely(bfs_error(ret)))
return print_bfs_bug(ret);
@@ -1922,16 +1987,6 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
if (!check_prev_add_irq(curr, prev, next))
return 0;
- /*
- * For recursive read-locks we do all the dependency checks,
- * but we dont store read-triggered dependencies (only
- * write-triggered dependencies). This ensures that only the
- * write-side dependencies matter, and that if for example a
- * write-lock never takes any other locks, then the reads are
- * equivalent to a NOP.
- */
- if (next->read == 2 || prev->read == 2)
- return 1;
/*
* Is the <prev> -> <next> dependency already present?
*
@@ -1944,6 +1999,7 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
if (entry->class == hlock_class(next)) {
if (distance == 1)
entry->distance = 1;
+ entry->dep |= calc_dep(prev->read, next->read);
return 1;
}
}
@@ -1953,6 +2009,7 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
*/
this.class = hlock_class(prev);
this.parent = NULL;
+ this.is_rr = (prev->read == 2);
ret = check_redundant(&this, hlock_class(next), &target_entry);
if (ret == BFS_RMATCH) {
debug_atomic_inc(nr_redundant);
@@ -1971,14 +2028,18 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
*/
ret = add_lock_to_list(hlock_class(next),
&hlock_class(prev)->locks_after,
- next->acquire_ip, distance, trace);
+ next->acquire_ip, distance,
+ calc_dep(prev->read, next->read),
+ trace);
if (!ret)
return 0;
ret = add_lock_to_list(hlock_class(prev),
&hlock_class(next)->locks_before,
- next->acquire_ip, distance, trace);
+ next->acquire_ip, distance,
+ calc_dep(next->read, prev->read),
+ trace);
if (!ret)
return 0;
@@ -2040,7 +2101,7 @@ check_prevs_add(struct task_struct *curr, struct held_lock *next)
* Only non-recursive-read entries get new dependencies
* added:
*/
- if (hlock->read != 2 && hlock->check) {
+ if (hlock->check) {
int ret = check_prev_add(curr, hlock, next,
distance, &trace, save);
if (!ret)
--
2.14.1
Powered by blists - more mailing lists