[tip: locking/core] locking/lockdep: Add a skip() function to __bfs()
The following commit has been merged into the locking/core branch of tip:
Commit-ID: bc2dd71b283665f0a409d5b6fc603d5a6fdc219e
Gitweb:
https://git.kernel.org/tip/bc2dd71b283665f0a409d5b6fc603d5a6fdc219e
Author:Boqun Feng
AuthorDate:Thu, 10 Dec 2020 11:02:40 +01:00
Committer: Peter Zijlstra
CommitterDate: Thu, 14 Jan 2021 11:20:17 +01:00
locking/lockdep: Add a skip() function to __bfs()
Some __bfs() walks will have additional iteration constraints (beyond
the path being strong). Provide an additional function to allow
terminating graph walks.
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
---
kernel/locking/lockdep.c | 29 +++--
1 file changed, 19 insertions(+), 10 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index b061e29..f50f026 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1672,6 +1672,7 @@ static inline struct lock_list *__bfs_next(struct
lock_list *lock, int offset)
static enum bfs_result __bfs(struct lock_list *source_entry,
void *data,
bool (*match)(struct lock_list *entry, void *data),
+bool (*skip)(struct lock_list *entry, void *data),
struct lock_list **target_entry,
int offset)
{
@@ -1732,7 +1733,12 @@ static enum bfs_result __bfs(struct lock_list
*source_entry,
/*
* Step 3: we haven't visited this and there is a strong
* dependency path to this, so check with @match.
+* If @skip is provide and returns true, we skip this
+* lock (and any path this lock is in).
*/
+ if (skip && skip(lock, data))
+ continue;
+
if (match(lock, data)) {
*target_entry = lock;
return BFS_RMATCH;
@@ -1775,9 +1781,10 @@ static inline enum bfs_result
__bfs_forwards(struct lock_list *src_entry,
void *data,
bool (*match)(struct lock_list *entry, void *data),
+ bool (*skip)(struct lock_list *entry, void *data),
struct lock_list **target_entry)
{
- return __bfs(src_entry, data, match, target_entry,
+ return __bfs(src_entry, data, match, skip, target_entry,
offsetof(struct lock_class, locks_after));
}
@@ -1786,9 +1793,10 @@ static inline enum bfs_result
__bfs_backwards(struct lock_list *src_entry,
void *data,
bool (*match)(struct lock_list *entry, void *data),
+ bool (*skip)(struct lock_list *entry, void *data),
struct lock_list **target_entry)
{
- return __bfs(src_entry, data, match, target_entry,
+ return __bfs(src_entry, data, match, skip, target_entry,
offsetof(struct lock_class, locks_before));
}
@@ -2019,7 +2027,7 @@ static unsigned long __lockdep_count_forward_deps(struct
lock_list *this)
unsigned long count = 0;
struct lock_list *target_entry;
- __bfs_forwards(this, (void *), noop_count, _entry);
+ __bfs_forwards(this, (void *), noop_count, NULL, _entry);
return count;
}
@@ -2044,7 +2052,7 @@ static unsigned long __lockdep_count_backward_deps(struct
lock_list *this)
unsigned long count = 0;
struct lock_list *target_entry;
- __bfs_backwards(this, (void *), noop_count, _entry);
+ __bfs_backwards(this, (void *), noop_count, NULL, _entry);
return count;
}
@@ -2072,11 +2080,12 @@ unsigned long lockdep_count_backward_deps(struct
lock_class *class)
static noinline enum bfs_result
check_path(struct held_lock *target, struct lock_list *src_entry,
bool (*match)(struct lock_list *entry, void *data),
+ bool (*skip)(struct lock_list *entry, void *data),
struct lock_list **target_entry)
{
enum bfs_result ret;
- ret = __bfs_forwards(src_entry, target, match, target_entry);
+ ret = __bfs_forwards(src_entry, target, match, skip, target_entry);
if (unlikely(bfs_error(ret)))
print_bfs_bug(ret);
@@ -2103,7 +2112,7 @@ check_noncircular(struct held_lock *src, struct held_lock
*target,
debug_atomic_inc(nr_cyclic_checks);
- ret = check_path(target, _entry, hlock_conflict, _entry);
+ ret = check_path(target, _entry, hlock_conflict, NULL,
_entry);
if (unlikely(ret == BFS_RMATCH)) {
if (!*trace) {
@@ -2152,7 +2161,7 @@ check_redundant(struct held_lock *src, struct held_lock
*target)
debug_atomic_inc(nr_redundant_checks);
- ret = check_path(target, _entry, hlock_equal, _entry);
+ ret = check_path(target, _entry, hlock_equal, NULL, _entry);
if (ret == BFS_RMATCH)
[tip: locking/core] lockdep/selftest: Add wait context selftests
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 9271a40d2a1429113160ccc4c16150921600bcc1
Gitweb:
https://git.kernel.org/tip/9271a40d2a1429113160ccc4c16150921600bcc1
Author:Boqun Feng
AuthorDate:Tue, 08 Dec 2020 18:31:12 +08:00
Committer: Peter Zijlstra
CommitterDate: Thu, 14 Jan 2021 11:20:16 +01:00
lockdep/selftest: Add wait context selftests
These tests are added for two purposes:
* Test the implementation of wait context checks and related
annotations.
* Semi-document the rules for wait context nesting when
PROVE_RAW_LOCK_NESTING=y.
The test cases are only avaible for PROVE_RAW_LOCK_NESTING=y, as wait
context checking makes more sense for that configuration.
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20201208103112.2838119-5-boqun.f...@gmail.com
---
lib/locking-selftest.c | 232 -
1 file changed, 232 insertions(+)
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index 9959ea2..23376ee 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -64,6 +64,9 @@ static DEFINE_SPINLOCK(lock_B);
static DEFINE_SPINLOCK(lock_C);
static DEFINE_SPINLOCK(lock_D);
+static DEFINE_RAW_SPINLOCK(raw_lock_A);
+static DEFINE_RAW_SPINLOCK(raw_lock_B);
+
static DEFINE_RWLOCK(rwlock_A);
static DEFINE_RWLOCK(rwlock_B);
static DEFINE_RWLOCK(rwlock_C);
@@ -1306,6 +1309,7 @@
GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion3_soft_wlock)
#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define I_SPINLOCK(x) lockdep_reset_lock(_##x.dep_map)
+# define I_RAW_SPINLOCK(x) lockdep_reset_lock(_lock_##x.dep_map)
# define I_RWLOCK(x) lockdep_reset_lock(_##x.dep_map)
# define I_MUTEX(x)lockdep_reset_lock(_##x.dep_map)
# define I_RWSEM(x)lockdep_reset_lock(_##x.dep_map)
@@ -1315,6 +1319,7 @@
GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion3_soft_wlock)
#endif
#else
# define I_SPINLOCK(x)
+# define I_RAW_SPINLOCK(x)
# define I_RWLOCK(x)
# define I_MUTEX(x)
# define I_RWSEM(x)
@@ -1358,9 +1363,12 @@ static void reset_locks(void)
I1(A); I1(B); I1(C); I1(D);
I1(X1); I1(X2); I1(Y1); I1(Y2); I1(Z1); I1(Z2);
I_WW(t); I_WW(t2); I_WW(o.base); I_WW(o2.base); I_WW(o3.base);
+ I_RAW_SPINLOCK(A); I_RAW_SPINLOCK(B);
lockdep_reset();
I2(A); I2(B); I2(C); I2(D);
init_shared_classes();
+ raw_spin_lock_init(_lock_A);
+ raw_spin_lock_init(_lock_B);
ww_mutex_init(, _lockdep); ww_mutex_init(, _lockdep);
ww_mutex_init(, _lockdep);
memset(, 0, sizeof(t)); memset(, 0, sizeof(t2));
@@ -2419,6 +2427,226 @@ static void fs_reclaim_tests(void)
pr_cont("\n");
}
+#define __guard(cleanup) __maybe_unused __attribute__((__cleanup__(cleanup)))
+
+static void hardirq_exit(int *_)
+{
+ HARDIRQ_EXIT();
+}
+
+#define HARDIRQ_CONTEXT(name, ...) \
+ int hardirq_guard_##name __guard(hardirq_exit); \
+ HARDIRQ_ENTER();
+
+#define NOTTHREADED_HARDIRQ_CONTEXT(name, ...) \
+ int notthreaded_hardirq_guard_##name __guard(hardirq_exit); \
+ local_irq_disable();\
+ __irq_enter(); \
+ WARN_ON(!in_irq());
+
+static void softirq_exit(int *_)
+{
+ SOFTIRQ_EXIT();
+}
+
+#define SOFTIRQ_CONTEXT(name, ...) \
+ int softirq_guard_##name __guard(softirq_exit); \
+ SOFTIRQ_ENTER();
+
+static void rcu_exit(int *_)
+{
+ rcu_read_unlock();
+}
+
+#define RCU_CONTEXT(name, ...) \
+ int rcu_guard_##name __guard(rcu_exit); \
+ rcu_read_lock();
+
+static void rcu_bh_exit(int *_)
+{
+ rcu_read_unlock_bh();
+}
+
+#define RCU_BH_CONTEXT(name, ...) \
+ int rcu_bh_guard_##name __guard(rcu_bh_exit); \
+ rcu_read_lock_bh();
+
+static void rcu_sched_exit(int *_)
+{
+ rcu_read_unlock_sched();
+}
+
+#define RCU_SCHED_CONTEXT(name, ...) \
+ int rcu_sched_guard_##name __guard(rcu_sched_exit); \
+ rcu_read_lock_sched();
+
+static void rcu_callback_exit(int *_)
+{
+ rcu_lock_release(_callback_map);
+}
+
+#define RCU_CALLBACK_CONTEXT(name, ...)
\
+ int rcu_callback_guard_##name __guard(rcu_callback_exit); \
+ rcu_lock_acquire(_callback_map);
+
+
+static void raw_spinlock_exit(raw_spinlock_t **lock)
+{
+ raw_spin_unlock(*lock);
+}
+
+#define RAW_SPINLOCK_CONTEXT(name, lock)
\
+ raw_spinlock_t *raw_spinlock_guard_##name __guard(raw_spinlock_exit) =
&(lock); \
+ raw_spin_lock(&(lock));
+
+static void spinlock_exit(spinlock_t **lock)
+{
[tip: locking/core] locking/lockdep: Exclude local_lock_t from IRQ inversions
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 5f2962401c6e195222f320d12b3a55377b2d4653
Gitweb:
https://git.kernel.org/tip/5f2962401c6e195222f320d12b3a55377b2d4653
Author:Boqun Feng
AuthorDate:Thu, 10 Dec 2020 11:15:00 +01:00
Committer: Peter Zijlstra
CommitterDate: Thu, 14 Jan 2021 11:20:17 +01:00
locking/lockdep: Exclude local_lock_t from IRQ inversions
The purpose of local_lock_t is to abstract: preempt_disable() /
local_bh_disable() / local_irq_disable(). These are the traditional
means of gaining access to per-cpu data, but are fundamentally
non-preemptible.
local_lock_t provides a per-cpu lock, that on !PREEMPT_RT reduces to
no-ops, just like regular spinlocks do on UP.
This gives rise to:
CPU0CPU1
local_lock(B) spin_lock_irq(A)
spin_lock(A) local_lock(B)
Where lockdep then figures things will lock up; which would be true if
B were any other kind of lock. However this is a false positive, no
such deadlock actually exists.
For !RT the above local_lock(B) is preempt_disable(), and there's
obviously no deadlock; alternatively, CPU0's B != CPU1's B.
For RT the argument is that since local_lock() nests inside
spin_lock(), it cannot be used in hardirq context, and therefore CPU0
cannot in fact happen. Even though B is a real lock, it is a
preemptible lock and any threaded-irq would simply schedule out and
let the preempted task (which holds B) continue such that the task on
CPU1 can make progress, after which the threaded-irq resumes and can
finish.
This means that we can never form an IRQ inversion on a local_lock
dependency, so terminate the graph walk when looking for IRQ
inversions when we encounter one.
One consequence is that (for LOCKDEP_SMALL) when we look for redundant
dependencies, A -> B is not redundant in the presence of A -> L -> B.
Signed-off-by: Boqun Feng
[peterz: Changelog]
Signed-off-by: Peter Zijlstra (Intel)
---
kernel/locking/lockdep.c | 57 ---
1 file changed, 53 insertions(+), 4 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index f2ae8a6..ad9afd8 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2200,6 +2200,44 @@ static inline bool usage_match(struct lock_list *entry,
void *mask)
return !!((entry->class->usage_mask & LOCKF_IRQ) & *(unsigned
long *)mask);
}
+static inline bool usage_skip(struct lock_list *entry, void *mask)
+{
+ /*
+* Skip local_lock() for irq inversion detection.
+*
+* For !RT, local_lock() is not a real lock, so it won't carry any
+* dependency.
+*
+* For RT, an irq inversion happens when we have lock A and B, and on
+* some CPU we can have:
+*
+* lock(A);
+*
+*lock(B);
+*
+* where lock(B) cannot sleep, and we have a dependency B -> ... -> A.
+*
+* Now we prove local_lock() cannot exist in that dependency. First we
+* have the observation for any lock chain L1 -> ... -> Ln, for any
+* 1 <= i <= n, Li.inner_wait_type <= L1.inner_wait_type, otherwise
+* wait context check will complain. And since B is not a sleep lock,
+* therefore B.inner_wait_type >= 2, and since the inner_wait_type of
+* local_lock() is 3, which is greater than 2, therefore there is no
+* way the local_lock() exists in the dependency B -> ... -> A.
+*
+* As a result, we will skip local_lock(), when we search for irq
+* inversion bugs.
+*/
+ if (entry->class->lock_type == LD_LOCK_PERCPU) {
+ if (DEBUG_LOCKS_WARN_ON(entry->class->wait_type_inner <
LD_WAIT_CONFIG))
+ return false;
+
+ return true;
+ }
+
+ return false;
+}
+
/*
* Find a node in the forwards-direction dependency sub-graph starting
* at @root->class that matches @bit.
@@ -2215,7 +2253,7 @@ find_usage_forwards(struct lock_list *root, unsigned long
usage_mask,
debug_atomic_inc(nr_find_usage_forwards_checks);
- result = __bfs_forwards(root, _mask, usage_match, NULL,
target_entry);
+ result = __bfs_forwards(root, _mask, usage_match, usage_skip,
target_entry);
return result;
}
@@ -2232,7 +2270,7 @@ find_usage_backwards(struct lock_list *root, unsigned
long usage_mask,
debug_atomic_inc(nr_find_usage_backwards_checks);
- result = __bfs_backwards(root, _mask, usage_match, NULL,
target_entry);
+ result = __bfs_backwards(root, _mask, usage_match, usage_skip,
target_entry);
return result;
}
@@ -2597,7 +2635,7 @@ static int check_irq_usage(struct task_struct *curr,
struct held_lock *prev,
*/
bfs_init_rootb(, prev);
- ret = __bfs_backwards(, _mask, usage_accumulate, NULL, NULL);
+
[tip: locking/core] lockdep/selftest: Add spin_nest_lock test
The following commit has been merged into the locking/core branch of tip:
Commit-ID: e04ce676e7aa490dcf5df880592e3db5e842a9bc
Gitweb:
https://git.kernel.org/tip/e04ce676e7aa490dcf5df880592e3db5e842a9bc
Author:Boqun Feng
AuthorDate:Mon, 02 Nov 2020 13:37:42 +08:00
Committer: Peter Zijlstra
CommitterDate: Thu, 03 Dec 2020 11:20:50 +01:00
lockdep/selftest: Add spin_nest_lock test
Add a self test case to test the behavior for the following case:
lock(A);
lock_nest_lock(C1, A);
lock(B);
lock_nest_lock(C2, A);
This is a reproducer for a problem[1] reported by Chris Wilson, and is
helpful to prevent this.
[1]:
https://lore.kernel.org/lkml/160390684819.31966.12048967113267928...@build.alporthouse.com/
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20201102053743.450459-2-boqun.f...@gmail.com
---
lib/locking-selftest.c | 17 +
1 file changed, 17 insertions(+)
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index afa7d4b..4c24ac8 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -2009,6 +2009,19 @@ static void ww_test_spin_nest_unlocked(void)
U(A);
}
+/* This is not a deadlock, because we have X1 to serialize Y1 and Y2 */
+static void ww_test_spin_nest_lock(void)
+{
+ spin_lock(_X1);
+ spin_lock_nest_lock(_Y1, _X1);
+ spin_lock(_A);
+ spin_lock_nest_lock(_Y2, _X1);
+ spin_unlock(_A);
+ spin_unlock(_Y2);
+ spin_unlock(_Y1);
+ spin_unlock(_X1);
+}
+
static void ww_test_unneeded_slow(void)
{
WWAI();
@@ -2226,6 +2239,10 @@ static void ww_tests(void)
dotest(ww_test_spin_nest_unlocked, FAILURE, LOCKTYPE_WW);
pr_cont("\n");
+ print_testname("spinlock nest test");
+ dotest(ww_test_spin_nest_lock, SUCCESS, LOCKTYPE_WW);
+ pr_cont("\n");
+
printk(" -\n");
printk(" |block | try |context|\n");
printk(" -\n");
[tip: locking/urgent] lockdep: Put graph lock/unlock under lock_recursion protection
The following commit has been merged into the locking/urgent branch of tip:
Commit-ID: 43be4388e94b915799a24f0eaf664bf95b85231f
Gitweb:
https://git.kernel.org/tip/43be4388e94b915799a24f0eaf664bf95b85231f
Author:Boqun Feng
AuthorDate:Fri, 13 Nov 2020 19:05:03 +08:00
Committer: Peter Zijlstra
CommitterDate: Tue, 17 Nov 2020 13:15:35 +01:00
lockdep: Put graph lock/unlock under lock_recursion protection
A warning was hit when running xfstests/generic/068 in a Hyper-V guest:
[...] [ cut here ]
[...] DEBUG_LOCKS_WARN_ON(lockdep_hardirqs_enabled())
[...] WARNING: CPU: 2 PID: 1350 at kernel/locking/lockdep.c:5280
check_flags.part.0+0x165/0x170
[...] ...
[...] Workqueue: events pwq_unbound_release_workfn
[...] RIP: 0010:check_flags.part.0+0x165/0x170
[...] ...
[...] Call Trace:
[...] lock_is_held_type+0x72/0x150
[...] ? lock_acquire+0x16e/0x4a0
[...] rcu_read_lock_sched_held+0x3f/0x80
[...] __send_ipi_one+0x14d/0x1b0
[...] hv_send_ipi+0x12/0x30
[...] __pv_queued_spin_unlock_slowpath+0xd1/0x110
[...] __raw_callee_save___pv_queued_spin_unlock_slowpath+0x11/0x20
[...] .slowpath+0x9/0xe
[...] lockdep_unregister_key+0x128/0x180
[...] pwq_unbound_release_workfn+0xbb/0xf0
[...] process_one_work+0x227/0x5c0
[...] worker_thread+0x55/0x3c0
[...] ? process_one_work+0x5c0/0x5c0
[...] kthread+0x153/0x170
[...] ? __kthread_bind_mask+0x60/0x60
[...] ret_from_fork+0x1f/0x30
The cause of the problem is we have call chain lockdep_unregister_key()
-> lockdep_unlock() ->
arch_spin_unlock() -> __pv_queued_spin_unlock_slowpath() -> pv_kick() ->
__send_ipi_one() -> trace_hyperv_send_ipi_one().
Although this particular warning is triggered because Hyper-V has a
trace point in ipi sending, but in general arch_spin_unlock() may call
another function having a trace point in it, so put the arch_spin_lock()
and arch_spin_unlock() after lock_recursion protection to fix this
problem and avoid similiar problems.
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20201113110512.1056501-1-boqun.f...@gmail.com
---
kernel/locking/lockdep.c | 6 --
1 file changed, 4 insertions(+), 2 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index d9fb9e1..c1418b4 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -108,19 +108,21 @@ static inline void lockdep_lock(void)
{
DEBUG_LOCKS_WARN_ON(!irqs_disabled());
+ __this_cpu_inc(lockdep_recursion);
arch_spin_lock(&__lock);
__owner = current;
- __this_cpu_inc(lockdep_recursion);
}
static inline void lockdep_unlock(void)
{
+ DEBUG_LOCKS_WARN_ON(!irqs_disabled());
+
if (debug_locks && DEBUG_LOCKS_WARN_ON(__owner != current))
return;
- __this_cpu_dec(lockdep_recursion);
__owner = NULL;
arch_spin_unlock(&__lock);
+ __this_cpu_dec(lockdep_recursion);
}
static inline bool lockdep_assert_locked(void)
[tip: locking/urgent] lockdep: Avoid to modify chain keys in validate_chain()
The following commit has been merged into the locking/urgent branch of tip:
Commit-ID: d61fc96a37603384cd531622c1e89de1096b5123
Gitweb:
https://git.kernel.org/tip/d61fc96a37603384cd531622c1e89de1096b5123
Author:Boqun Feng
AuthorDate:Mon, 02 Nov 2020 13:37:41 +08:00
Committer: Peter Zijlstra
CommitterDate: Tue, 10 Nov 2020 18:38:38 +01:00
lockdep: Avoid to modify chain keys in validate_chain()
Chris Wilson reported a problem spotted by check_chain_key(): a chain
key got changed in validate_chain() because we modify the ->read in
validate_chain() to skip checks for dependency adding, and ->read is
taken into calculation for chain key since commit f611e8cf98ec
("lockdep: Take read/write status in consideration when generate
chainkey").
Fix this by avoiding to modify ->read in validate_chain() based on two
facts: a) since we now support recursive read lock detection, there is
no need to skip checks for dependency adding for recursive readers, b)
since we have a), there is only one case left (nest_lock) where we want
to skip checks in validate_chain(), we simply remove the modification
for ->read and rely on the return value of check_deadlock() to skip the
dependency adding.
Reported-by: Chris Wilson
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20201102053743.450459-1-boqun.f...@gmail.com
---
kernel/locking/lockdep.c | 19 +--
1 file changed, 9 insertions(+), 10 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index b71ad8d..d9fb9e1 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2765,7 +2765,9 @@ print_deadlock_bug(struct task_struct *curr, struct
held_lock *prev,
* (Note that this has to be done separately, because the graph cannot
* detect such classes of deadlocks.)
*
- * Returns: 0 on deadlock detected, 1 on OK, 2 on recursive read
+ * Returns: 0 on deadlock detected, 1 on OK, 2 if another lock with the same
+ * lock class is held but nest_lock is also held, i.e. we rely on the
+ * nest_lock to avoid the deadlock.
*/
static int
check_deadlock(struct task_struct *curr, struct held_lock *next)
@@ -2788,7 +2790,7 @@ check_deadlock(struct task_struct *curr, struct held_lock
*next)
* lock class (i.e. read_lock(lock)+read_lock(lock)):
*/
if ((next->read == 2) && prev->read)
- return 2;
+ continue;
/*
* We're holding the nest_lock, which serializes this lock's
@@ -3593,15 +3595,12 @@ static int validate_chain(struct task_struct *curr,
if (!ret)
return 0;
/*
-* Mark recursive read, as we jump over it when
-* building dependencies (just like we jump over
-* trylock entries):
-*/
- if (ret == 2)
- hlock->read = 2;
- /*
* Add dependency only if this lock is not the head
-* of the chain, and if it's not a secondary read-lock:
+* of the chain, and if the new lock introduces no more
+* lock dependency (because we already hold a lock with the
+* same lock class) nor deadlock (because the nest_lock
+* serializes nesting locks), see the comments for
+* check_deadlock().
*/
if (!chain_head && ret != 2) {
if (!check_prevs_add(curr, hlock))
[tip: locking/core] lockdep: Optimize the memory usage of circular queue
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 6d1823ccc480866e571ab1206665d693aeb600cf
Gitweb:
https://git.kernel.org/tip/6d1823ccc480866e571ab1206665d693aeb600cf
Author:Boqun Feng
AuthorDate:Thu, 17 Sep 2020 16:01:50 +08:00
Committer: Peter Zijlstra
CommitterDate: Tue, 29 Sep 2020 09:56:59 +02:00
lockdep: Optimize the memory usage of circular queue
Qian Cai reported a BFS_EQUEUEFULL warning [1] after read recursive
deadlock detection merged into tip tree recently. Unlike the previous
lockep graph searching, which iterate every lock class (every node in
the graph) exactly once, the graph searching for read recurisve deadlock
detection needs to iterate every lock dependency (every edge in the
graph) once, as a result, the maximum memory cost of the circular queue
changes from O(V), where V is the number of lock classes (nodes or
vertices) in the graph, to O(E), where E is the number of lock
dependencies (edges), because every lock class or dependency gets
enqueued once in the BFS. Therefore we hit the BFS_EQUEUEFULL case.
However, actually we don't need to enqueue all dependencies for the BFS,
because every time we enqueue a dependency, we almostly enqueue all
other dependencies in the same dependency list ("almostly" is because
we currently check before enqueue, so if a dependency doesn't pass the
check stage we won't enqueue it, however, we can always do in reverse
ordering), based on this, we can only enqueue the first dependency from
a dependency list and every time we want to fetch a new dependency to
work, we can either:
1)fetch the dependency next to the current dependency in the
dependency list
or
2)if the dependency in 1) doesn't exist, fetch the dependency from
the queue.
With this approach, the "max bfs queue depth" for a x86_64_defconfig +
lockdep and selftest config kernel can get descreased from:
max bfs queue depth: 201
to (after apply this patch)
max bfs queue depth: 61
While I'm at it, clean up the code logic a little (e.g. directly return
other than set a "ret" value and goto the "exit" label).
[1]:
https://lore.kernel.org/lkml/17343f6f7f2438fc376125384133c5ba70c2a681.ca...@redhat.com/
Reported-by: Qian Cai
Reported-by: syzbot+62ebe501c1ce9a91f...@syzkaller.appspotmail.com
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200917080210.108095-1-boqun.f...@gmail.com
---
kernel/locking/lockdep.c | 99 +++---
1 file changed, 60 insertions(+), 39 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index cccf4bc..9560a4e 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1606,6 +1606,15 @@ static inline void bfs_init_rootb(struct lock_list *lock,
lock->only_xr = (hlock->read != 0);
}
+static inline struct lock_list *__bfs_next(struct lock_list *lock, int offset)
+{
+ if (!lock || !lock->parent)
+ return NULL;
+
+ return list_next_or_null_rcu(get_dep_list(lock->parent, offset),
+>entry, struct lock_list, entry);
+}
+
/*
* Breadth-First Search to find a strong path in the dependency graph.
*
@@ -1639,36 +1648,25 @@ static enum bfs_result __bfs(struct lock_list
*source_entry,
struct lock_list **target_entry,
int offset)
{
+ struct circular_queue *cq = _cq;
+ struct lock_list *lock = NULL;
struct lock_list *entry;
- struct lock_list *lock;
struct list_head *head;
- struct circular_queue *cq = _cq;
- enum bfs_result ret = BFS_RNOMATCH;
+ unsigned int cq_depth;
+ bool first;
lockdep_assert_locked();
- if (match(source_entry, data)) {
- *target_entry = source_entry;
- ret = BFS_RMATCH;
- goto exit;
- }
-
- head = get_dep_list(source_entry, offset);
- if (list_empty(head))
- goto exit;
-
__cq_init(cq);
__cq_enqueue(cq, source_entry);
- while ((lock = __cq_dequeue(cq))) {
- bool prev_only_xr;
-
- if (!lock->class) {
- ret = BFS_EINVALIDNODE;
- goto exit;
- }
+ while ((lock = __bfs_next(lock, offset)) || (lock = __cq_dequeue(cq))) {
+ if (!lock->class)
+ return BFS_EINVALIDNODE;
/*
+* Step 1: check whether we already finish on this one.
+*
* If we have visited all the dependencies from this @lock to
* others (iow, if we have visited all lock_list entries in
* @lock->class->locks_{after,before}) we skip, otherwise go
@@ -1680,13 +1678,13 @@ static enum bfs_result __bfs(struct
[tip: locking/core] lockdep/selftest: Unleash irq_read_recursion2 and add more
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 31e0d747708272356bee9b6a1b90c1e6525b0f6d
Gitweb:
https://git.kernel.org/tip/31e0d747708272356bee9b6a1b90c1e6525b0f6d
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:34 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:06 +02:00
lockdep/selftest: Unleash irq_read_recursion2 and add more
Now since we can handle recursive read related irq inversion deadlocks
correctly, uncomment the irq_read_recursion2 and add more testcases.
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-16-boqun.f...@gmail.com
---
lib/locking-selftest.c | 59 -
1 file changed, 47 insertions(+), 12 deletions(-)
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index 002d1ec..f65a658 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -1053,20 +1053,28 @@ GENERATE_PERMUTATIONS_3_EVENTS(irq_inversion_soft_wlock)
#define E3() \
\
IRQ_ENTER();\
- RL(A); \
+ LOCK(A);\
L(B); \
U(B); \
- RU(A); \
+ UNLOCK(A); \
IRQ_EXIT();
/*
- * Generate 12 testcases:
+ * Generate 24 testcases:
*/
#include "locking-selftest-hardirq.h"
-GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_hard)
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_hard_rlock)
+
+#include "locking-selftest-wlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_hard_wlock)
#include "locking-selftest-softirq.h"
-GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_soft)
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_soft_rlock)
+
+#include "locking-selftest-wlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_soft_wlock)
#undef E1
#undef E2
@@ -1080,8 +1088,8 @@ GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_soft)
\
IRQ_DISABLE(); \
L(B); \
- WL(A); \
- WU(A); \
+ LOCK(A);\
+ UNLOCK(A); \
U(B); \
IRQ_ENABLE();
@@ -1098,13 +1106,21 @@ GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_soft)
IRQ_EXIT();
/*
- * Generate 12 testcases:
+ * Generate 24 testcases:
*/
#include "locking-selftest-hardirq.h"
-// GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_hard)
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_hard_rlock)
+
+#include "locking-selftest-wlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_hard_wlock)
#include "locking-selftest-softirq.h"
-// GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_soft)
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_soft_rlock)
+
+#include "locking-selftest-wlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_soft_wlock)
#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define I_SPINLOCK(x) lockdep_reset_lock(_##x.dep_map)
@@ -1257,6 +1273,25 @@ static inline void print_testname(const char *testname)
dotest(name##_rlock_##nr, SUCCESS, LOCKTYPE_RWLOCK);\
pr_cont("\n");
+#define DO_TESTCASE_2RW(desc, name, nr)\
+ print_testname(desc"/"#nr); \
+ pr_cont(" |"); \
+ dotest(name##_wlock_##nr, FAILURE, LOCKTYPE_RWLOCK);\
+ dotest(name##_rlock_##nr, SUCCESS, LOCKTYPE_RWLOCK);\
+ pr_cont("\n");
+
+#define DO_TESTCASE_2x2RW(desc, name, nr) \
+ DO_TESTCASE_2RW("hard-"desc, name##_hard, nr) \
+ DO_TESTCASE_2RW("soft-"desc, name##_soft, nr) \
+
+#define DO_TESTCASE_6x2x2RW(desc, name)\
+ DO_TESTCASE_2x2RW(desc, name, 123); \
+ DO_TESTCASE_2x2RW(desc, name, 132); \
+ DO_TESTCASE_2x2RW(desc, name, 213); \
+ DO_TESTCASE_2x2RW(desc, name, 231); \
+ DO_TESTCASE_2x2RW(desc, name, 312); \
+ DO_TESTCASE_2x2RW(desc, name, 321);
+
#define DO_TESTCASE_6(desc, name) \
print_testname(desc); \
dotest(name##_spin, FAILURE, LOCKTYPE_SPIN);\
@@ -2121,8 +2156,8 @@ void locking_selftest(void)
DO_TESTCASE_6x6("safe-A + unsafe-B #2", irqsafe4);
DO_TESTCASE_6x6RW("irq
[tip: locking/core] lockdep: Take read/write status in consideration when generate chainkey
The following commit has been merged into the locking/core branch of tip:
Commit-ID: f611e8cf98ec908b9c2c0da6064a660fc6022487
Gitweb:
https://git.kernel.org/tip/f611e8cf98ec908b9c2c0da6064a660fc6022487
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:33 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:06 +02:00
lockdep: Take read/write status in consideration when generate chainkey
Currently, the chainkey of a lock chain is a hash sum of the class_idx
of all the held locks, the read/write status are not taken in to
consideration while generating the chainkey. This could result into a
problem, if we have:
P1()
{
read_lock(B);
lock(A);
}
P2()
{
lock(A);
read_lock(B);
}
P3()
{
lock(A);
write_lock(B);
}
, and P1(), P2(), P3() run one by one. And when running P2(), lockdep
detects such a lock chain A -> B is not a deadlock, then it's added in
the chain cache, and then when running P3(), even if it's a deadlock, we
could miss it because of the hit of chain cache. This could be confirmed
by self testcase "chain cached mixed R-L/L-W ".
To resolve this, we use concept "hlock_id" to generate the chainkey, the
hlock_id is a tuple (hlock->class_idx, hlock->read), which fits in a u16
type. With this, the chainkeys are different is the lock sequences have
the same locks but different read/write status.
Besides, since we use "hlock_id" to generate chainkeys, the chain_hlocks
array now store the "hlock_id"s rather than lock_class indexes.
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-15-boqun.f...@gmail.com
---
kernel/locking/lockdep.c | 53 +--
1 file changed, 35 insertions(+), 18 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index b87766e..cccf4bc 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -372,6 +372,21 @@ static struct hlist_head classhash_table[CLASSHASH_SIZE];
static struct hlist_head chainhash_table[CHAINHASH_SIZE];
/*
+ * the id of held_lock
+ */
+static inline u16 hlock_id(struct held_lock *hlock)
+{
+ BUILD_BUG_ON(MAX_LOCKDEP_KEYS_BITS + 2 > 16);
+
+ return (hlock->class_idx | (hlock->read << MAX_LOCKDEP_KEYS_BITS));
+}
+
+static inline unsigned int chain_hlock_class_idx(u16 hlock_id)
+{
+ return hlock_id & (MAX_LOCKDEP_KEYS - 1);
+}
+
+/*
* The hash key of the lock dependency chains is a hash itself too:
* it's a hash of all locks taken up to that lock, including that lock.
* It's a 64-bit hash, because it's important for the keys to be
@@ -3202,7 +3217,10 @@ static inline void free_chain_hlocks(int base, int size)
struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
{
- return lock_classes + chain_hlocks[chain->base + i];
+ u16 chain_hlock = chain_hlocks[chain->base + i];
+ unsigned int class_idx = chain_hlock_class_idx(chain_hlock);
+
+ return lock_classes + class_idx - 1;
}
/*
@@ -3228,12 +3246,12 @@ static inline int get_first_held_lock(struct
task_struct *curr,
/*
* Returns the next chain_key iteration
*/
-static u64 print_chain_key_iteration(int class_idx, u64 chain_key)
+static u64 print_chain_key_iteration(u16 hlock_id, u64 chain_key)
{
- u64 new_chain_key = iterate_chain_key(chain_key, class_idx);
+ u64 new_chain_key = iterate_chain_key(chain_key, hlock_id);
- printk(" class_idx:%d -> chain_key:%016Lx",
- class_idx,
+ printk(" hlock_id:%d -> chain_key:%016Lx",
+ (unsigned int)hlock_id,
(unsigned long long)new_chain_key);
return new_chain_key;
}
@@ -3250,12 +3268,12 @@ print_chain_keys_held_locks(struct task_struct *curr,
struct held_lock *hlock_ne
hlock_next->irq_context);
for (; i < depth; i++) {
hlock = curr->held_locks + i;
- chain_key = print_chain_key_iteration(hlock->class_idx,
chain_key);
+ chain_key = print_chain_key_iteration(hlock_id(hlock),
chain_key);
print_lock(hlock);
}
- print_chain_key_iteration(hlock_next->class_idx, chain_key);
+ print_chain_key_iteration(hlock_id(hlock_next), chain_key);
print_lock(hlock_next);
}
@@ -3263,14 +3281,14 @@ static void print_chain_keys_chain(struct lock_chain
*chain)
{
int i;
u64 chain_key = INITIAL_CHAIN_KEY;
- int class_id;
+ u16 hlock_id;
printk("depth: %u\n", chain->depth);
for (i = 0; i < chain->depth; i++) {
- class_id = chain_hlocks[chain->base + i];
- chain_key = print_chain_key_iteration(class_id, chain_key);
+ hlock_id = chain_hlocks[chain->base + i];
+
[tip: locking/core] lockdep/selftest: Add a R-L/L-W test case specific to chain cache behavior
The following commit has been merged into the locking/core branch of tip:
Commit-ID: d4f200e579e96051f1f081f795820787826eb234
Gitweb:
https://git.kernel.org/tip/d4f200e579e96051f1f081f795820787826eb234
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:32 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:06 +02:00
lockdep/selftest: Add a R-L/L-W test case specific to chain cache behavior
As our chain cache doesn't differ read/write locks, so even we can
detect a read-lock/lock-write deadlock in check_noncircular(), we can
still be fooled if a read-lock/lock-read case(which is not a deadlock)
comes first.
So introduce this test case to test specific to the chain cache behavior
on detecting recursive read lock related deadlocks.
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-14-boqun.f...@gmail.com
---
lib/locking-selftest.c | 47 +-
1 file changed, 47 insertions(+)
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index caadc4d..002d1ec 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -400,6 +400,49 @@ static void rwsem_ABBA1(void)
* read_lock(A)
* spin_lock(B)
* spin_lock(B)
+ * write_lock(A)
+ *
+ * This test case is aimed at poking whether the chain cache prevents us from
+ * detecting a read-lock/lock-write deadlock: if the chain cache doesn't differ
+ * read/write locks, the following case may happen
+ *
+ * { read_lock(A)->lock(B) dependency exists }
+ *
+ * P0:
+ * lock(B);
+ * read_lock(A);
+ *
+ * { Not a deadlock, B -> A is added in the chain cache }
+ *
+ * P1:
+ * lock(B);
+ * write_lock(A);
+ *
+ * { B->A found in chain cache, not reported as a deadlock }
+ *
+ */
+static void rlock_chaincache_ABBA1(void)
+{
+ RL(X1);
+ L(Y1);
+ U(Y1);
+ RU(X1);
+
+ L(Y1);
+ RL(X1);
+ RU(X1);
+ U(Y1);
+
+ L(Y1);
+ WL(X1);
+ WU(X1);
+ U(Y1); // should fail
+}
+
+/*
+ * read_lock(A)
+ * spin_lock(B)
+ * spin_lock(B)
* read_lock(A)
*/
static void rlock_ABBA2(void)
@@ -2062,6 +2105,10 @@ void locking_selftest(void)
pr_cont(" |");
dotest(rwsem_ABBA3, FAILURE, LOCKTYPE_RWSEM);
+ print_testname("chain cached mixed R-L/L-W ABBA");
+ pr_cont(" |");
+ dotest(rlock_chaincache_ABBA1, FAILURE, LOCKTYPE_RWLOCK);
+
printk("
--\n");
/*
[tip: locking/core] lockdep: Fix recursive read lock related safe->unsafe detection
The following commit has been merged into the locking/core branch of tip:
Commit-ID: f08e3888574d490b31481eef6d84c61bedba7a47
Gitweb:
https://git.kernel.org/tip/f08e3888574d490b31481eef6d84c61bedba7a47
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:30 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:05 +02:00
lockdep: Fix recursive read lock related safe->unsafe detection
Currently, in safe->unsafe detection, lockdep misses the fact that a
LOCK_ENABLED_IRQ_*_READ usage and a LOCK_USED_IN_IRQ_*_READ usage may
cause deadlock too, for example:
P1 P2
write_lock(l1);
read_lock(l2);
write_lock(l2);
read_lock(l1);
Actually, all of the following cases may cause deadlocks:
LOCK_USED_IN_IRQ_* -> LOCK_ENABLED_IRQ_*
LOCK_USED_IN_IRQ_*_READ -> LOCK_ENABLED_IRQ_*
LOCK_USED_IN_IRQ_* -> LOCK_ENABLED_IRQ_*_READ
LOCK_USED_IN_IRQ_*_READ -> LOCK_ENABLED_IRQ_*_READ
To fix this, we need to 1) change the calculation of exclusive_mask() so
that READ bits are not dropped and 2) always call usage() in
mark_lock_irq() to check usage deadlocks, even when the new usage of the
lock is READ.
Besides, adjust usage_match() and usage_acculumate() to recursive read
lock changes.
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-12-boqun.f...@gmail.com
---
kernel/locking/lockdep.c | 188 --
1 file changed, 141 insertions(+), 47 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 42e2f1f..6644974 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2100,22 +2100,72 @@ check_redundant(struct held_lock *src, struct held_lock
*target)
#ifdef CONFIG_TRACE_IRQFLAGS
+/*
+ * Forwards and backwards subgraph searching, for the purposes of
+ * proving that two subgraphs can be connected by a new dependency
+ * without creating any illegal irq-safe -> irq-unsafe lock dependency.
+ *
+ * A irq safe->unsafe deadlock happens with the following conditions:
+ *
+ * 1) We have a strong dependency path A -> ... -> B
+ *
+ * 2) and we have ENABLED_IRQ usage of B and USED_IN_IRQ usage of A, therefore
+ *irq can create a new dependency B -> A (consider the case that a holder
+ *of B gets interrupted by an irq whose handler will try to acquire A).
+ *
+ * 3) the dependency circle A -> ... -> B -> A we get from 1) and 2) is a
+ *strong circle:
+ *
+ * For the usage bits of B:
+ *a) if A -> B is -(*N)->, then B -> A could be any type, so any
+ * ENABLED_IRQ usage suffices.
+ *b) if A -> B is -(*R)->, then B -> A must be -(E*)->, so only
+ * ENABLED_IRQ_*_READ usage suffices.
+ *
+ * For the usage bits of A:
+ *c) if A -> B is -(E*)->, then B -> A could be any type, so any
+ * USED_IN_IRQ usage suffices.
+ *d) if A -> B is -(S*)->, then B -> A must be -(*N)->, so only
+ * USED_IN_IRQ_*_READ usage suffices.
+ */
+
+/*
+ * There is a strong dependency path in the dependency graph: A -> B, and now
+ * we need to decide which usage bit of A should be accumulated to detect
+ * safe->unsafe bugs.
+ *
+ * Note that usage_accumulate() is used in backwards search, so ->only_xr
+ * stands for whether A -> B only has -(S*)-> (in this case ->only_xr is true).
+ *
+ * As above, if only_xr is false, which means A -> B has -(E*)-> dependency
+ * path, any usage of A should be considered. Otherwise, we should only
+ * consider _READ usage.
+ */
static inline bool usage_accumulate(struct lock_list *entry, void *mask)
{
- *(unsigned long *)mask |= entry->class->usage_mask;
+ if (!entry->only_xr)
+ *(unsigned long *)mask |= entry->class->usage_mask;
+ else /* Mask out _READ usage bits */
+ *(unsigned long *)mask |= (entry->class->usage_mask &
LOCKF_IRQ);
return false;
}
/*
- * Forwards and backwards subgraph searching, for the purposes of
- * proving that two subgraphs can be connected by a new dependency
- * without creating any illegal irq-safe -> irq-unsafe lock dependency.
+ * There is a strong dependency path in the dependency graph: A -> B, and now
+ * we need to decide which usage bit of B conflicts with the usage bits of A,
+ * i.e. which usage bit of B may introduce safe->unsafe deadlocks.
+ *
+ * As above, if only_xr is false, which means A -> B has -(*N)-> dependency
+ * path, any usage of B should be considered. Otherwise, we should only
+ * consider _READ usage.
*/
-
static inline bool usage_match(struct lock_list *entry, void *mask)
{
- return !!(entry->class->usage_mask & *(unsigned long *)mask);
+ if (!entry->only_xr)
+ return
[tip: locking/core] lockdep: Support deadlock detection for recursive read locks in check_noncircular()
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 9de0c9bbcedf752e762c67f105bff342e30f9105
Gitweb:
https://git.kernel.org/tip/9de0c9bbcedf752e762c67f105bff342e30f9105
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:28 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:05 +02:00
lockdep: Support deadlock detection for recursive read locks in
check_noncircular()
Currently, lockdep only has limit support for deadlock detection for
recursive read locks.
This patch support deadlock detection for recursive read locks. The
basic idea is:
We are about to add dependency B -> A in to the dependency graph, we use
check_noncircular() to find whether we have a strong dependency path
A -> .. -> B so that we have a strong dependency circle (a closed strong
dependency path):
A -> .. -> B -> A
, which doesn't have two adjacent dependencies as -(*R)-> L -(S*)->.
Since A -> .. -> B is already a strong dependency path, so if either
B -> A is -(E*)-> or A -> .. -> B is -(*N)->, the circle A -> .. -> B ->
A is strong, otherwise not. So we introduce a new match function
hlock_conflict() to replace the class_equal() for the deadlock check in
check_noncircular().
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-10-boqun.f...@gmail.com
---
kernel/locking/lockdep.c | 43 +++
1 file changed, 35 insertions(+), 8 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 78cd74d..9160f1d 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1838,10 +1838,37 @@ static inline bool class_equal(struct lock_list *entry,
void *data)
return entry->class == data;
}
+/*
+ * We are about to add B -> A into the dependency graph, and in __bfs() a
+ * strong dependency path A -> .. -> B is found: hlock_class equals
+ * entry->class.
+ *
+ * We will have a deadlock case (conflict) if A -> .. -> B -> A is a strong
+ * dependency cycle, that means:
+ *
+ * Either
+ *
+ * a) B -> A is -(E*)->
+ *
+ * or
+ *
+ * b) A -> .. -> B is -(*N)-> (i.e. A -> .. -(*N)-> B)
+ *
+ * as then we don't have -(*R)-> -(S*)-> in the cycle.
+ */
+static inline bool hlock_conflict(struct lock_list *entry, void *data)
+{
+ struct held_lock *hlock = (struct held_lock *)data;
+
+ return hlock_class(hlock) == entry->class && /* Found A -> .. -> B */
+ (hlock->read == 0 || /* B -> A is -(E*)-> */
+ !entry->only_xr); /* A -> .. -> B is -(*N)-> */
+}
+
static noinline void print_circular_bug(struct lock_list *this,
- struct lock_list *target,
- struct held_lock *check_src,
- struct held_lock *check_tgt)
+ struct lock_list *target,
+ struct held_lock *check_src,
+ struct held_lock *check_tgt)
{
struct task_struct *curr = current;
struct lock_list *parent;
@@ -1950,13 +1977,13 @@ unsigned long lockdep_count_backward_deps(struct
lock_class *class)
* or not.
*/
static noinline enum bfs_result
-check_path(struct lock_class *target, struct lock_list *src_entry,
+check_path(struct held_lock *target, struct lock_list *src_entry,
+ bool (*match)(struct lock_list *entry, void *data),
struct lock_list **target_entry)
{
enum bfs_result ret;
- ret = __bfs_forwards(src_entry, (void *)target, class_equal,
-target_entry);
+ ret = __bfs_forwards(src_entry, target, match, target_entry);
if (unlikely(bfs_error(ret)))
print_bfs_bug(ret);
@@ -1983,7 +2010,7 @@ check_noncircular(struct held_lock *src, struct held_lock
*target,
debug_atomic_inc(nr_cyclic_checks);
- ret = check_path(hlock_class(target), _entry, _entry);
+ ret = check_path(target, _entry, hlock_conflict, _entry);
if (unlikely(ret == BFS_RMATCH)) {
if (!*trace) {
@@ -2021,7 +2048,7 @@ check_redundant(struct held_lock *src, struct held_lock
*target)
debug_atomic_inc(nr_redundant_checks);
- ret = check_path(hlock_class(target), _entry, _entry);
+ ret = check_path(target, _entry, class_equal, _entry);
if (ret == BFS_RMATCH)
debug_atomic_inc(nr_redundant);
[tip: locking/core] lockdep: Add recursive read locks into dependency graph
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 621c9dac0eea7607cb9a57cc9ba47fbcd4e644c9
Gitweb:
https://git.kernel.org/tip/621c9dac0eea7607cb9a57cc9ba47fbcd4e644c9
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:31 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:06 +02:00
lockdep: Add recursive read locks into dependency graph
Since we have all the fundamental to handle recursive read locks, we now
add them into the dependency graph.
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-13-boqun.f...@gmail.com
---
kernel/locking/lockdep.c | 19 ++-
1 file changed, 2 insertions(+), 17 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 6644974..b87766e 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2809,16 +2809,6 @@ check_prev_add(struct task_struct *curr, struct
held_lock *prev,
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 -> dependency already present?
*
* (this may occur even though this is a new chain: consider
@@ -2935,13 +2925,8 @@ check_prevs_add(struct task_struct *curr, struct
held_lock *next)
u16 distance = curr->lockdep_depth - depth + 1;
hlock = curr->held_locks + depth - 1;
- /*
-* Only non-recursive-read entries get new dependencies
-* added:
-*/
- if (hlock->read != 2 && hlock->check) {
- int ret = check_prev_add(curr, hlock, next, distance,
-);
+ if (hlock->check) {
+ int ret = check_prev_add(curr, hlock, next, distance,
);
if (!ret)
return 0;
[tip: locking/core] lockdep/selftest: Introduce recursion3
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 96a16f45aed89cf024606a11679b0609d09552c7
Gitweb:
https://git.kernel.org/tip/96a16f45aed89cf024606a11679b0609d09552c7
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:38 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:08 +02:00
lockdep/selftest: Introduce recursion3
Add a test case shows that USED_IN_*_READ and ENABLE_*_READ can cause
deadlock too.
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-20-boqun.f...@gmail.com
---
lib/locking-selftest.c | 55 +-
1 file changed, 55 insertions(+)
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index 17f8f6f..a899b3f 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -1249,6 +1249,60 @@
GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_soft_rlock)
#include "locking-selftest-wlock.h"
GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_soft_wlock)
+#undef E1
+#undef E2
+#undef E3
+/*
+ * read-lock / write-lock recursion that is unsafe.
+ *
+ * A is a ENABLED_*_READ lock
+ * B is a USED_IN_*_READ lock
+ *
+ * read_lock(A);
+ * write_lock(B);
+ *
+ * read_lock(B);
+ * write_lock(A); // if this one is read_lock(), no
deadlock
+ */
+
+#define E1() \
+ \
+ IRQ_DISABLE(); \
+ WL(B); \
+ LOCK(A);\
+ UNLOCK(A); \
+ WU(B); \
+ IRQ_ENABLE();
+
+#define E2() \
+ \
+ RL(A); \
+ RU(A); \
+
+#define E3() \
+ \
+ IRQ_ENTER();\
+ RL(B); \
+ RU(B); \
+ IRQ_EXIT();
+
+/*
+ * Generate 24 testcases:
+ */
+#include "locking-selftest-hardirq.h"
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion3_hard_rlock)
+
+#include "locking-selftest-wlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion3_hard_wlock)
+
+#include "locking-selftest-softirq.h"
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion3_soft_rlock)
+
+#include "locking-selftest-wlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion3_soft_wlock)
+
#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define I_SPINLOCK(x) lockdep_reset_lock(_##x.dep_map)
# define I_RWLOCK(x) lockdep_reset_lock(_##x.dep_map)
@@ -2413,6 +2467,7 @@ void locking_selftest(void)
DO_TESTCASE_6x2x2RW("irq read-recursion", irq_read_recursion);
DO_TESTCASE_6x2x2RW("irq read-recursion #2", irq_read_recursion2);
+ DO_TESTCASE_6x2x2RW("irq read-recursion #3", irq_read_recursion3);
ww_tests();
[tip: locking/core] lockdep: Make __bfs() visit every dependency until a match
The following commit has been merged into the locking/core branch of tip:
Commit-ID: d563bc6ead9e79be37067d58509a605b67378184
Gitweb:
https://git.kernel.org/tip/d563bc6ead9e79be37067d58509a605b67378184
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:23 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:03 +02:00
lockdep: Make __bfs() visit every dependency until a match
Currently, __bfs() will do a breadth-first search in the dependency
graph and visit each lock class in the graph exactly once, so for
example, in the following graph:
A -> B
|^
||
+--> C
a __bfs() call starts at A, will visit B through dependency A -> B and
visit C through dependency A -> C and that's it, IOW, __bfs() will not
visit dependency C -> B.
This is OK for now, as we only have strong dependencies in the
dependency graph, so whenever there is a traverse path from A to B in
__bfs(), it means A has strong dependencies to B (IOW, B depends on A
strongly). So no need to visit all dependencies in the graph.
However, as we are going to add recursive-read lock into the dependency
graph, as a result, not all the paths mean strong dependencies, in the
same example above, dependency A -> B may be a weak dependency and
traverse A -> C -> B may be a strong dependency path. And with the old
way of __bfs() (i.e. visiting every lock class exactly once), we will
miss the strong dependency path, which will result into failing to find
a deadlock. To cure this for the future, we need to find a way for
__bfs() to visit each dependency, rather than each class, exactly once
in the search until we find a match.
The solution is simple:
We used to mark lock_class::lockdep_dependency_gen_id to indicate a
class has been visited in __bfs(), now we change the semantics a little
bit: we now mark lock_class::lockdep_dependency_gen_id to indicate _all
the dependencies_ in its lock_{after,before} have been visited in the
__bfs() (note we only take one direction in a __bfs() search). In this
way, every dependency is guaranteed to be visited until we find a match.
Note: the checks in mark_lock_accessed() and lock_accessed() are
removed, because after this modification, we may call these two
functions on @source_entry of __bfs(), which may not be the entry in
"list_entries"
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-5-boqun.f...@gmail.com
---
kernel/locking/lockdep.c | 61 ++-
1 file changed, 35 insertions(+), 26 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 462c68c..150686a 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1421,23 +1421,19 @@ static inline unsigned int __cq_get_elem_count(struct
circular_queue *cq)
return (cq->rear - cq->front) & CQ_MASK;
}
-static inline void mark_lock_accessed(struct lock_list *lock,
- struct lock_list *parent)
+static inline void mark_lock_accessed(struct lock_list *lock)
{
- unsigned long nr;
+ lock->class->dep_gen_id = lockdep_dependency_gen_id;
+}
- nr = lock - list_entries;
- WARN_ON(nr >= ARRAY_SIZE(list_entries)); /* Out-of-bounds, input fail */
+static inline void visit_lock_entry(struct lock_list *lock,
+ struct lock_list *parent)
+{
lock->parent = parent;
- lock->class->dep_gen_id = lockdep_dependency_gen_id;
}
static inline unsigned long lock_accessed(struct lock_list *lock)
{
- unsigned long nr;
-
- nr = lock - list_entries;
- WARN_ON(nr >= ARRAY_SIZE(list_entries)); /* Out-of-bounds, input fail */
return lock->class->dep_gen_id == lockdep_dependency_gen_id;
}
@@ -1540,26 +1536,39 @@ static enum bfs_result __bfs(struct lock_list
*source_entry,
goto exit;
}
+ /*
+* If we have visited all the dependencies from this @lock to
+* others (iow, if we have visited all lock_list entries in
+* @lock->class->locks_{after,before}) we skip, otherwise go
+* and visit all the dependencies in the list and mark this
+* list accessed.
+*/
+ if (lock_accessed(lock))
+ continue;
+ else
+ mark_lock_accessed(lock);
+
head = get_dep_list(lock, offset);
+ DEBUG_LOCKS_WARN_ON(!irqs_disabled());
+
list_for_each_entry_rcu(entry, head, entry) {
- if (!lock_accessed(entry)) {
- unsigned int cq_depth;
- mark_lock_accessed(entry, lock);
- if (match(entry, data)) {
-
[tip: locking/core] lockdep: Extend __bfs() to work with multiple types of dependencies
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 6971c0f345620aae5e6172207a57b7524603a34e
Gitweb:
https://git.kernel.org/tip/6971c0f345620aae5e6172207a57b7524603a34e
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:26 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:04 +02:00
lockdep: Extend __bfs() to work with multiple types of dependencies
Now we have four types of dependencies in the dependency graph, and not
all the pathes carry real dependencies (the dependencies that may cause
a deadlock), for example:
Given lock A and B, if we have:
CPU1CPU2
= ==
write_lock(A); read_lock(B);
read_lock(B); write_lock(A);
(assuming read_lock(B) is a recursive reader)
then we have dependencies A -(ER)-> B, and B -(SN)-> A, and a
dependency path A -(ER)-> B -(SN)-> A.
In lockdep w/o recursive locks, a dependency path from A to A
means a deadlock. However, the above case is obviously not a
deadlock, because no one holds B exclusively, therefore no one
waits for the other to release B, so who get A first in CPU1 and
CPU2 will run non-blockingly.
As a result, dependency path A -(ER)-> B -(SN)-> A is not a
real/strong dependency that could cause a deadlock.
>From the observation above, we know that for a dependency path to be
real/strong, no two adjacent dependencies can be as -(*R)-> -(S*)->.
Now our mission is to make __bfs() traverse only the strong dependency
paths, which is simple: we record whether we only have -(*R)-> for the
previous lock_list of the path in lock_list::only_xr, and when we pick a
dependency in the traverse, we 1) filter out -(S*)-> dependency if the
previous lock_list only has -(*R)-> dependency (i.e. ->only_xr is true)
and 2) set the next lock_list::only_xr to true if we only have -(*R)->
left after we filter out dependencies based on 1), otherwise, set it to
false.
With this extension for __bfs(), we now need to initialize the root of
__bfs() properly (with a correct ->only_xr), 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
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-8-boqun.f...@gmail.com
---
include/linux/lockdep.h | 2 +-
kernel/locking/lockdep.c | 113 +++---
2 files changed, 96 insertions(+), 19 deletions(-)
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 35c8bb0..57d642d 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -57,6 +57,8 @@ struct lock_list {
u16 distance;
/* bitmap of different dependencies from head to this */
u8 dep;
+ /* used by BFS to record whether "prev -> this" only has -(*R)-> */
+ u8 only_xr;
/*
* 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 16ad1b7..5abc227 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1551,8 +1551,72 @@ static inline u8 calc_depb(struct held_lock *prev,
struct held_lock *next)
}
/*
- * Forward- or backward-dependency search, used for both circular dependency
- * checking and hardirq-unsafe/softirq-unsafe checking.
+ * 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->only_xr = 0;
+}
+
+/*
+ * Initialize a lock_list entry @lock based on a lock acquisition @hlock as the
+ * root for a BFS search.
+ *
+ * ->only_xr of the initial lock node is set to @hlock->read == 2, to make sure
+ * that -> @hlock and @hlock -> is not -(*R)->
+ * and -(S*)->.
+ */
+static inline void bfs_init_root(struct lock_list *lock,
+struct held_lock *hlock)
+{
+ __bfs_init_root(lock, hlock_class(hlock));
+ lock->only_xr = (hlock->read == 2);
+}
+
+/*
+ * Similar to bfs_init_root() but initialize the root for backwards BFS.
+ *
+ * ->only_xr of the initial lock node is set to @hlock->read != 0, to make sure
+ * that -> @hlock and @hlock -> is not
+ * -(*S)-> and -(R*)-> (reverse order of -(*R)-> and -(S*)->).
+ */
+static inline void bfs_init_rootb(struct lock_list *lock,
+ struct held_lock *hlock)
+{
+ __bfs_init_root(lock, hlock_class(hlock));
+ lock->only_xr = (hlock->read != 0);
+}
+
+/*
+ * Breadth-First Search to find a strong path in the dependency graph.
+ *
+ *
[tip: locking/core] lockdep: Demagic the return value of BFS
The following commit has been merged into the locking/core branch of tip:
Commit-ID: b11be024de164213f6338973d76ab9ab139120cd
Gitweb:
https://git.kernel.org/tip/b11be024de164213f6338973d76ab9ab139120cd
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:22 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:03 +02:00
lockdep: Demagic the return value of BFS
__bfs() could return four magic numbers:
1: search succeeds, but none match.
0: search succeeds, find one match.
-1: search fails because of the cq is full.
-2: search fails because a invalid node is found.
This patch cleans things up by using a enum type for the return value
of __bfs() and its friends, this improves the code readability of the
code, and further, could help if we want to extend the BFS.
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-4-boqun.f...@gmail.com
---
kernel/locking/lockdep.c | 155 +-
1 file changed, 89 insertions(+), 66 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 77cd9e6..462c68c 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1471,28 +1471,58 @@ static inline struct list_head *get_dep_list(struct
lock_list *lock, int offset)
return lock_class + offset;
}
+/*
+ * Return values of a bfs search:
+ *
+ * BFS_E* indicates an error
+ * BFS_R* indicates a result (match or not)
+ *
+ * BFS_EINVALIDNODE: Find a invalid node in the graph.
+ *
+ * BFS_EQUEUEFULL: The queue is full while doing the bfs.
+ *
+ * BFS_RMATCH: Find the matched node in the graph, and put that node into
+ * *@target_entry.
+ *
+ * BFS_RNOMATCH: Haven't found the matched node and keep *@target_entry
+ * _unchanged_.
+ */
+enum bfs_result {
+ BFS_EINVALIDNODE = -2,
+ BFS_EQUEUEFULL = -1,
+ BFS_RMATCH = 0,
+ BFS_RNOMATCH = 1,
+};
+
+/*
+ * bfs_result < 0 means error
+ */
+static inline bool bfs_error(enum bfs_result res)
+{
+ return res < 0;
+}
/*
* Forward- or backward-dependency search, used for both circular dependency
* checking and hardirq-unsafe/softirq-unsafe checking.
*/
-static int __bfs(struct lock_list *source_entry,
-void *data,
-int (*match)(struct lock_list *entry, void *data),
-struct lock_list **target_entry,
-int offset)
+static enum bfs_result __bfs(struct lock_list *source_entry,
+void *data,
+int (*match)(struct lock_list *entry, void *data),
+struct lock_list **target_entry,
+int offset)
{
struct lock_list *entry;
struct lock_list *lock;
struct list_head *head;
struct circular_queue *cq = _cq;
- int ret = 1;
+ enum bfs_result ret = BFS_RNOMATCH;
lockdep_assert_locked();
if (match(source_entry, data)) {
*target_entry = source_entry;
- ret = 0;
+ ret = BFS_RMATCH;
goto exit;
}
@@ -1506,7 +1536,7 @@ static int __bfs(struct lock_list *source_entry,
while ((lock = __cq_dequeue(cq))) {
if (!lock->class) {
- ret = -2;
+ ret = BFS_EINVALIDNODE;
goto exit;
}
@@ -1518,12 +1548,12 @@ static int __bfs(struct lock_list *source_entry,
mark_lock_accessed(entry, lock);
if (match(entry, data)) {
*target_entry = entry;
- ret = 0;
+ ret = BFS_RMATCH;
goto exit;
}
if (__cq_enqueue(cq, entry)) {
- ret = -1;
+ ret = BFS_EQUEUEFULL;
goto exit;
}
cq_depth = __cq_get_elem_count(cq);
@@ -1536,20 +1566,22 @@ exit:
return ret;
}
-static inline int __bfs_forwards(struct lock_list *src_entry,
- void *data,
- int (*match)(struct lock_list *entry, void *data),
- struct lock_list **target_entry)
+static inline enum bfs_result
+__bfs_forwards(struct lock_list *src_entry,
+ void *data,
+ int (*match)(struct lock_list *entry, void *data),
+ struct lock_list **target_entry)
{
return __bfs(src_entry, data, match, target_entry,
offsetof(struct lock_class, locks_after));
}
-static inline int __bfs_backwards(struct lock_list
[tip: locking/core] lockdep/Documention: Recursive read lock detection reasoning
The following commit has been merged into the locking/core branch of tip: Commit-ID: 224ec489d3cdb0af6794e25739d98dc9c5b2 Gitweb: https://git.kernel.org/tip/224ec489d3cdb0af6794e25739d98dc9c5b2 Author:Boqun Feng AuthorDate:Fri, 07 Aug 2020 15:42:21 +08:00 Committer: Peter Zijlstra CommitterDate: Wed, 26 Aug 2020 12:42:03 +02:00 lockdep/Documention: Recursive read lock detection reasoning This patch add the documentation piece for the reasoning of deadlock detection related to recursive read lock. The following sections are added: * Explain what is a recursive read lock, and what deadlock cases they could introduce. * Introduce the notations for different types of dependencies, and the definition of strong paths. * Proof for a closed strong path is both sufficient and necessary for deadlock detections with recursive read locks involved. The proof could also explain why we call the path "strong" Signed-off-by: Boqun Feng Signed-off-by: Peter Zijlstra (Intel) Link: https://lkml.kernel.org/r/20200807074238.1632519-3-boqun.f...@gmail.com --- Documentation/locking/lockdep-design.rst | 258 ++- 1 file changed, 258 insertions(+) diff --git a/Documentation/locking/lockdep-design.rst b/Documentation/locking/lockdep-design.rst index 23fcbc4..cec03bd 100644 --- a/Documentation/locking/lockdep-design.rst +++ b/Documentation/locking/lockdep-design.rst @@ -392,3 +392,261 @@ Run the command and save the output, then compare against the output from a later run of this command to identify the leakers. This same output can also help you find situations where runtime lock initialization has been omitted. + +Recursive read locks: +- +The whole of the rest document tries to prove a certain type of cycle is equivalent +to deadlock possibility. + +There are three types of lockers: writers (i.e. exclusive lockers, like +spin_lock() or write_lock()), non-recursive readers (i.e. shared lockers, like +down_read()) and recursive readers (recursive shared lockers, like rcu_read_lock()). +And we use the following notations of those lockers in the rest of the document: + + W or E: stands for writers (exclusive lockers). + r: stands for non-recursive readers. + R: stands for recursive readers. + S: stands for all readers (non-recursive + recursive), as both are shared lockers. + N: stands for writers and non-recursive readers, as both are not recursive. + +Obviously, N is "r or W" and S is "r or R". + +Recursive readers, as their name indicates, are the lockers allowed to acquire +even inside the critical section of another reader of the same lock instance, +in other words, allowing nested read-side critical sections of one lock instance. + +While non-recursive readers will cause a self deadlock if trying to acquire inside +the critical section of another reader of the same lock instance. + +The difference between recursive readers and non-recursive readers is because: +recursive readers get blocked only by a write lock *holder*, while non-recursive +readers could get blocked by a write lock *waiter*. Considering the follow example: + + TASK A: TASK B: + + read_lock(X); + write_lock(X); + read_lock_2(X); + +Task A gets the reader (no matter whether recursive or non-recursive) on X via +read_lock() first. And when task B tries to acquire writer on X, it will block +and become a waiter for writer on X. Now if read_lock_2() is recursive readers, +task A will make progress, because writer waiters don't block recursive readers, +and there is no deadlock. However, if read_lock_2() is non-recursive readers, +it will get blocked by writer waiter B, and cause a self deadlock. + +Block conditions on readers/writers of the same lock instance: +-- +There are simply four block conditions: + +1. Writers block other writers. +2. Readers block writers. +3. Writers block both recursive readers and non-recursive readers. +4. And readers (recursive or not) don't block other recursive readers but + may block non-recursive readers (because of the potential co-existing + writer waiters) + +Block condition matrix, Y means the row blocks the column, and N means otherwise. + + | E | r | R | + +---+---+---+---+ + E | Y | Y | Y | + +---+---+---+---+ + r | Y | Y | N | + +---+---+---+---+ + R | Y | Y | N | + + (W: writers, r: non-recursive readers, R: recursive readers) + + +acquired recursively. Unlike non-recursive read locks, recursive read locks +only get blocked by current write lock *holders* other than write lock +*waiters*, for example: + + TASK A: TASK B: + + read_lock(X); + + write_lock(X);
[tip: locking/core] lockdep: Reduce the size of lock_list::distance
The following commit has been merged into the locking/core branch of tip:
Commit-ID: bd76eca10de2eb9998d5125b08e8997cbf5508d5
Gitweb:
https://git.kernel.org/tip/bd76eca10de2eb9998d5125b08e8997cbf5508d5
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:24 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:04 +02:00
lockdep: Reduce the size of lock_list::distance
lock_list::distance is always not greater than MAX_LOCK_DEPTH (which
is 48 right now), so a u16 will fit. This patch reduces the size of
lock_list::distance to save space, so that we can introduce other fields
to help detect recursive read lock deadlocks without increasing the size
of lock_list structure.
Suggested-by: Peter Zijlstra
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-6-boqun.f...@gmail.com
---
include/linux/lockdep.h | 2 +-
kernel/locking/lockdep.c | 6 +++---
2 files changed, 4 insertions(+), 4 deletions(-)
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 7cae5ea..2275010 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -54,7 +54,7 @@ struct lock_list {
struct lock_class *class;
struct lock_class *links_to;
const struct lock_trace *trace;
- int distance;
+ u16 distance;
/*
* 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 150686a..668a983 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1320,7 +1320,7 @@ static struct lock_list *alloc_list_entry(void)
*/
static int add_lock_to_list(struct lock_class *this,
struct lock_class *links_to, struct list_head *head,
- unsigned long ip, int distance,
+ unsigned long ip, u16 distance,
const struct lock_trace *trace)
{
struct lock_list *entry;
@@ -2489,7 +2489,7 @@ check_deadlock(struct task_struct *curr, struct held_lock
*next)
*/
static int
check_prev_add(struct task_struct *curr, struct held_lock *prev,
- struct held_lock *next, int distance,
+ struct held_lock *next, u16 distance,
struct lock_trace **const trace)
{
struct lock_list *entry;
@@ -2622,7 +2622,7 @@ check_prevs_add(struct task_struct *curr, struct
held_lock *next)
goto out_bug;
for (;;) {
- int distance = curr->lockdep_depth - depth + 1;
+ u16 distance = curr->lockdep_depth - depth + 1;
hlock = curr->held_locks + depth - 1;
/*
[tip: locking/core] locking: More accurate annotations for read_lock()
The following commit has been merged into the locking/core branch of tip:
Commit-ID: e918188611f073063415f40fae568fa4d86d9044
Gitweb:
https://git.kernel.org/tip/e918188611f073063415f40fae568fa4d86d9044
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:20 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:02 +02:00
locking: More accurate annotations for read_lock()
On the archs using QUEUED_RWLOCKS, read_lock() is not always a recursive
read lock, actually it's only recursive if in_interrupt() is true. So
change the annotation accordingly to catch more deadlocks.
Note we used to treat read_lock() as pure recursive read locks in
lib/locking-seftest.c, and this is useful, especially for the lockdep
development selftest, so we keep this via a variable to force switching
lock annotation for read_lock().
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-2-boqun.f...@gmail.com
---
include/linux/lockdep.h | 23 ++-
kernel/locking/lockdep.c | 14 ++
lib/locking-selftest.c | 11 +++
3 files changed, 47 insertions(+), 1 deletion(-)
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 6a584b3..7cae5ea 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -469,6 +469,20 @@ static inline void print_irqtrace_events(struct
task_struct *curr)
}
#endif
+/* Variable used to make lockdep treat read_lock() as recursive in selftests */
+#ifdef CONFIG_DEBUG_LOCKING_API_SELFTESTS
+extern unsigned int force_read_lock_recursive;
+#else /* CONFIG_DEBUG_LOCKING_API_SELFTESTS */
+#define force_read_lock_recursive 0
+#endif /* CONFIG_DEBUG_LOCKING_API_SELFTESTS */
+
+#ifdef CONFIG_LOCKDEP
+extern bool read_lock_is_recursive(void);
+#else /* CONFIG_LOCKDEP */
+/* If !LOCKDEP, the value is meaningless */
+#define read_lock_is_recursive() 0
+#endif
+
/*
* For trivial one-depth nesting of a lock-class, the following
* global define can be used. (Subsystems with multiple levels
@@ -490,7 +504,14 @@ static inline void print_irqtrace_events(struct
task_struct *curr)
#define spin_release(l, i) lock_release(l, i)
#define rwlock_acquire(l, s, t, i) lock_acquire_exclusive(l, s, t,
NULL, i)
-#define rwlock_acquire_read(l, s, t, i)
lock_acquire_shared_recursive(l, s, t, NULL, i)
+#define rwlock_acquire_read(l, s, t, i)
\
+do { \
+ if (read_lock_is_recursive()) \
+ lock_acquire_shared_recursive(l, s, t, NULL, i);\
+ else\
+ lock_acquire_shared(l, s, t, NULL, i); \
+} while (0)
+
#define rwlock_release(l, i) lock_release(l, i)
#define seqcount_acquire(l, s, t, i) lock_acquire_exclusive(l, s, t,
NULL, i)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 54b74fa..77cd9e6 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4968,6 +4968,20 @@ static bool lockdep_nmi(void)
}
/*
+ * read_lock() is recursive if:
+ * 1. We force lockdep think this way in selftests or
+ * 2. The implementation is not queued read/write lock or
+ * 3. The locker is at an in_interrupt() context.
+ */
+bool read_lock_is_recursive(void)
+{
+ return force_read_lock_recursive ||
+ !IS_ENABLED(CONFIG_QUEUED_RWLOCKS) ||
+ in_interrupt();
+}
+EXPORT_SYMBOL_GPL(read_lock_is_recursive);
+
+/*
* We are not always called with irqs disabled - do that here,
* and also avoid lockdep recursion:
*/
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index 14f44f5..caadc4d 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -28,6 +28,7 @@
* Change this to 1 if you want to see the failure printouts:
*/
static unsigned int debug_locks_verbose;
+unsigned int force_read_lock_recursive;
static DEFINE_WD_CLASS(ww_lockdep);
@@ -1979,6 +1980,11 @@ void locking_selftest(void)
}
/*
+* treats read_lock() as recursive read locks for testing purpose
+*/
+ force_read_lock_recursive = 1;
+
+ /*
* Run the testsuite:
*/
printk("\n");
@@ -2073,6 +2079,11 @@ void locking_selftest(void)
ww_tests();
+ force_read_lock_recursive = 0;
+ /*
+* queued_read_lock() specific test cases can be put here
+*/
+
if (unexpected_testcase_failures) {
printk("-\n");
debug_locks = 0;
[tip: locking/core] lockdep: Introduce lock_list::dep
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 3454a36d6a39186de508dd43df590a6363364176
Gitweb:
https://git.kernel.org/tip/3454a36d6a39186de508dd43df590a6363364176
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:25 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:04 +02:00
lockdep: Introduce lock_list::dep
To add recursive read locks into the dependency graph, we need to store
the types of dependencies for the BFS later. There are four types of
dependencies:
* Exclusive -> Non-recursive dependencies: EN
e.g. write_lock(prev) held and try to acquire write_lock(next)
or non-recursive read_lock(next), which can be represented as
"prev -(EN)-> next"
* Shared -> Non-recursive dependencies: SN
e.g. read_lock(prev) held and try to acquire write_lock(next) or
non-recursive read_lock(next), which can be represented as
"prev -(SN)-> next"
* Exclusive -> Recursive dependencies: ER
e.g. write_lock(prev) held and try to acquire recursive
read_lock(next), which can be represented as "prev -(ER)-> next"
* Shared -> Recursive dependencies: SR
e.g. read_lock(prev) held and try to acquire recursive
read_lock(next), which can be represented as "prev -(SR)-> next"
So we use 4 bits for the presence of each type in lock_list::dep. Helper
functions and macros are also introduced to convert a pair of locks into
lock_list::dep bit and maintain the addition of different types of
dependencies.
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-7-boqun.f...@gmail.com
---
include/linux/lockdep.h | 2 +-
kernel/locking/lockdep.c | 92 +--
2 files changed, 90 insertions(+), 4 deletions(-)
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 2275010..35c8bb0 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -55,6 +55,8 @@ struct lock_list {
struct lock_class *links_to;
const struct lock_trace *trace;
u16 distance;
+ /* bitmap of different dependencies from head to this */
+ u8 dep;
/*
* 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 668a983..16ad1b7 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1320,7 +1320,7 @@ static struct lock_list *alloc_list_entry(void)
*/
static int add_lock_to_list(struct lock_class *this,
struct lock_class *links_to, struct list_head *head,
- unsigned long ip, u16 distance,
+ unsigned long ip, u16 distance, u8 dep,
const struct lock_trace *trace)
{
struct lock_list *entry;
@@ -1334,6 +1334,7 @@ static int add_lock_to_list(struct lock_class *this,
entry->class = this;
entry->links_to = links_to;
+ entry->dep = dep;
entry->distance = distance;
entry->trace = trace;
/*
@@ -1499,6 +1500,57 @@ static inline bool bfs_error(enum bfs_result res)
}
/*
+ * DEP_*_BIT in lock_list::dep
+ *
+ * For dependency @prev -> @next:
+ *
+ * SR: @prev is shared reader (->read != 0) and @next is recursive reader
+ * (->read == 2)
+ * ER: @prev is exclusive locker (->read == 0) and @next is recursive reader
+ * SN: @prev is shared reader and @next is non-recursive locker (->read != 2)
+ * EN: @prev is exclusive locker and @next is non-recursive locker
+ *
+ * Note that we define the value of DEP_*_BITs so that:
+ * bit0 is prev->read == 0
+ * bit1 is next->read != 2
+ */
+#define DEP_SR_BIT (0 + (0 << 1)) /* 0 */
+#define DEP_ER_BIT (1 + (0 << 1)) /* 1 */
+#define DEP_SN_BIT (0 + (1 << 1)) /* 2 */
+#define DEP_EN_BIT (1 + (1 << 1)) /* 3 */
+
+#define DEP_SR_MASK (1U << (DEP_SR_BIT))
+#define DEP_ER_MASK (1U << (DEP_ER_BIT))
+#define DEP_SN_MASK (1U << (DEP_SN_BIT))
+#define DEP_EN_MASK (1U << (DEP_EN_BIT))
+
+static inline unsigned int
+__calc_dep_bit(struct held_lock *prev, struct held_lock *next)
+{
+ return (prev->read == 0) + ((next->read != 2) << 1);
+}
+
+static inline u8 calc_dep(struct held_lock *prev, struct held_lock *next)
+{
+ return 1U << __calc_dep_bit(prev, next);
+}
+
+/*
+ * calculate the dep_bit for backwards edges. We care about whether @prev is
+ * shared and whether @next is recursive.
+ */
+static inline unsigned int
+__calc_dep_bitb(struct held_lock *prev, struct held_lock *next)
+{
+ return (next->read != 2) + ((prev->read == 0) << 1);
+}
+
+static inline u8 calc_depb(struct held_lock *prev, struct held_lock *next)
+{
+ return 1U << __calc_dep_bitb(prev, next);
+}
+
+/*
* Forward- or backward-dependency
[tip: locking/core] lockdep: Adjust check_redundant() for recursive read change
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 68e305678583f13a67e2ce22088c2520bd4f97b4
Gitweb:
https://git.kernel.org/tip/68e305678583f13a67e2ce22088c2520bd4f97b4
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:29 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:05 +02:00
lockdep: Adjust check_redundant() for recursive read change
check_redundant() will report redundancy if it finds a path could
replace the about-to-add dependency in the BFS search. With recursive
read lock changes, we certainly need to change the match function for
the check_redundant(), because the path needs to match not only the lock
class but also the dependency kinds. For example, if the about-to-add
dependency @prev -> @next is A -(SN)-> B, and we find a path A -(S*)->
.. -(*R)->B in the dependency graph with __bfs() (for simplicity, we can
also say we find an -(SR)-> path from A to B), we can not replace the
dependency with that path in the BFS search. Because the -(SN)->
dependency can make a strong path with a following -(S*)-> dependency,
however an -(SR)-> path cannot.
Further, we can replace an -(SN)-> dependency with a -(EN)-> path, that
means if we find a path which is stronger than or equal to the
about-to-add dependency, we can report the redundancy. By "stronger", it
means both the start and the end of the path are not weaker than the
start and the end of the dependency (E is "stronger" than S and N is
"stronger" than R), so that we can replace the dependency with that
path.
To make sure we find a path whose start point is not weaker than the
about-to-add dependency, we use a trick: the ->only_xr of the root
(start point) of __bfs() is initialized as @prev-> == 0, therefore if
@prev is E, __bfs() will pick only -(E*)-> for the first dependency,
otherwise, __bfs() can pick -(E*)-> or -(S*)-> for the first dependency.
To make sure we find a path whose end point is not weaker than the
about-to-add dependency, we replace the match function for __bfs()
check_redundant(), we check for the case that either @next is R
(anything is not weaker than it) or the end point of the path is N
(which is not weaker than anything).
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-11-boqun.f...@gmail.com
---
kernel/locking/lockdep.c | 47 ---
1 file changed, 44 insertions(+), 3 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 9160f1d..42e2f1f 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1833,9 +1833,39 @@ print_circular_bug_header(struct lock_list *entry,
unsigned int depth,
print_circular_bug_entry(entry, depth);
}
-static inline bool class_equal(struct lock_list *entry, void *data)
+/*
+ * We are about to add A -> B into the dependency graph, and in __bfs() a
+ * strong dependency path A -> .. -> B is found: hlock_class equals
+ * entry->class.
+ *
+ * If A -> .. -> B can replace A -> B in any __bfs() search (means the former
+ * is _stronger_ than or equal to the latter), we consider A -> B as redundant.
+ * For example if A -> .. -> B is -(EN)-> (i.e. A -(E*)-> .. -(*N)-> B), and A
+ * -> B is -(ER)-> or -(EN)->, then we don't need to add A -> B into the
+ * dependency graph, as any strong path ..-> A -> B ->.. we can get with
+ * having dependency A -> B, we could already get a equivalent path ..-> A ->
+ * .. -> B -> .. with A -> .. -> B. Therefore A -> B is reduntant.
+ *
+ * We need to make sure both the start and the end of A -> .. -> B is not
+ * weaker than A -> B. For the start part, please see the comment in
+ * check_redundant(). For the end part, we need:
+ *
+ * Either
+ *
+ * a) A -> B is -(*R)-> (everything is not weaker than that)
+ *
+ * or
+ *
+ * b) A -> .. -> B is -(*N)-> (nothing is stronger than this)
+ *
+ */
+static inline bool hlock_equal(struct lock_list *entry, void *data)
{
- return entry->class == data;
+ struct held_lock *hlock = (struct held_lock *)data;
+
+ return hlock_class(hlock) == entry->class && /* Found A -> .. -> B */
+ (hlock->read == 2 || /* A -> B is -(*R)-> */
+ !entry->only_xr); /* A -> .. -> B is -(*N)-> */
}
/*
@@ -2045,10 +2075,21 @@ check_redundant(struct held_lock *src, struct held_lock
*target)
struct lock_list src_entry;
bfs_init_root(_entry, src);
+ /*
+* Special setup for check_redundant().
+*
+* To report redundant, we need to find a strong dependency path that
+* is equal to or stronger than -> . So if is E,
+* we need to let __bfs() only search for a path starting at a -(E*)->,
+* we achieve this by setting the initial node's ->only_xr to true in
+* that case. And if is S, we set initial ->only_xr to false
+* because both -(S*)-> (equal) and -(E*)->
[tip: locking/core] lockdep/selftest: Add more recursive read related test cases
The following commit has been merged into the locking/core branch of tip: Commit-ID: 8ef7ca75120a39167def40f41daefee013c4b5af Gitweb: https://git.kernel.org/tip/8ef7ca75120a39167def40f41daefee013c4b5af Author:Boqun Feng AuthorDate:Fri, 07 Aug 2020 15:42:35 +08:00 Committer: Peter Zijlstra CommitterDate: Wed, 26 Aug 2020 12:42:07 +02:00 lockdep/selftest: Add more recursive read related test cases Add those four test cases: 1. X --(ER)--> Y --(ER)--> Z --(ER)--> X is deadlock. 2. X --(EN)--> Y --(SR)--> Z --(ER)--> X is deadlock. 3. X --(EN)--> Y --(SR)--> Z --(SN)--> X is not deadlock. 4. X --(ER)--> Y --(SR)--> Z --(EN)--> X is not deadlock. Those self testcases are valuable for the development of supporting recursive read related deadlock detection. Signed-off-by: Boqun Feng Signed-off-by: Peter Zijlstra (Intel) Link: https://lkml.kernel.org/r/20200807074238.1632519-17-boqun.f...@gmail.com --- lib/locking-selftest.c | 161 - 1 file changed, 161 insertions(+) diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c index f65a658..76c314a 100644 --- a/lib/locking-selftest.c +++ b/lib/locking-selftest.c @@ -1035,6 +1035,133 @@ GENERATE_PERMUTATIONS_3_EVENTS(irq_inversion_soft_wlock) #undef E3 /* + * write-read / write-read / write-read deadlock even if read is recursive + */ + +#define E1() \ + \ + WL(X1); \ + RL(Y1); \ + RU(Y1); \ + WU(X1); + +#define E2() \ + \ + WL(Y1); \ + RL(Z1); \ + RU(Z1); \ + WU(Y1); + +#define E3() \ + \ + WL(Z1); \ + RL(X1); \ + RU(X1); \ + WU(Z1); + +#include "locking-selftest-rlock.h" +GENERATE_PERMUTATIONS_3_EVENTS(W1R2_W2R3_W3R1) + +#undef E1 +#undef E2 +#undef E3 + +/* + * write-write / read-read / write-read deadlock even if read is recursive + */ + +#define E1() \ + \ + WL(X1); \ + WL(Y1); \ + WU(Y1); \ + WU(X1); + +#define E2() \ + \ + RL(Y1); \ + RL(Z1); \ + RU(Z1); \ + RU(Y1); + +#define E3() \ + \ + WL(Z1); \ + RL(X1); \ + RU(X1); \ + WU(Z1); + +#include "locking-selftest-rlock.h" +GENERATE_PERMUTATIONS_3_EVENTS(W1W2_R2R3_W3R1) + +#undef E1 +#undef E2 +#undef E3 + +/* + * write-write / read-read / read-write is not deadlock when read is recursive + */ + +#define E1() \ + \ + WL(X1); \ + WL(Y1); \ + WU(Y1); \ + WU(X1); + +#define E2() \ + \ + RL(Y1); \ + RL(Z1); \ + RU(Z1); \ + RU(Y1); + +#define E3() \ + \ + RL(Z1); \ + WL(X1); \ + WU(X1); \ + RU(Z1); + +#include "locking-selftest-rlock.h" +GENERATE_PERMUTATIONS_3_EVENTS(W1R2_R2R3_W3W1) + +#undef E1 +#undef E2 +#undef E3 + +/* + * write-read / read-read / write-write is not deadlock when read is recursive + */ + +#define E1() \ + \ + WL(X1); \ + RL(Y1); \ + RU(Y1); \ + WU(X1); + +#define E2() \ + \ + RL(Y1); \ + RL(Z1); \ + RU(Z1); \ + RU(Y1); + +#define E3() \ + \ + WL(Z1); \ + WL(X1); \ + WU(X1); \ + WU(Z1); + +#include "locking-selftest-rlock.h" +GENERATE_PERMUTATIONS_3_EVENTS(W1W2_R2R3_R3W1) + +#undef E1 +#undef E2 +#undef E3 +/* * read-lock / write-lock recursion that is actually safe. */ @@ -1259,6 +1386,19 @@ static
[tip: locking/core] lockdep: Make __bfs(.match) return bool
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 61775ed243433ff0556c4f76905929fe01e92922
Gitweb:
https://git.kernel.org/tip/61775ed243433ff0556c4f76905929fe01e92922
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:27 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:05 +02:00
lockdep: Make __bfs(.match) return bool
The "match" parameter of __bfs() is used for checking whether we hit a
match in the search, therefore it should return a boolean value rather
than an integer for better readability.
This patch then changes the return type of the function parameter and the
match functions to bool.
Suggested-by: Peter Zijlstra
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-9-boqun.f...@gmail.com
---
kernel/locking/lockdep.c | 20 ++--
1 file changed, 10 insertions(+), 10 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 5abc227..78cd74d 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1620,7 +1620,7 @@ static inline void bfs_init_rootb(struct lock_list *lock,
*/
static enum bfs_result __bfs(struct lock_list *source_entry,
void *data,
-int (*match)(struct lock_list *entry, void *data),
+bool (*match)(struct lock_list *entry, void *data),
struct lock_list **target_entry,
int offset)
{
@@ -1711,7 +1711,7 @@ exit:
static inline enum bfs_result
__bfs_forwards(struct lock_list *src_entry,
void *data,
- int (*match)(struct lock_list *entry, void *data),
+ bool (*match)(struct lock_list *entry, void *data),
struct lock_list **target_entry)
{
return __bfs(src_entry, data, match, target_entry,
@@ -1722,7 +1722,7 @@ __bfs_forwards(struct lock_list *src_entry,
static inline enum bfs_result
__bfs_backwards(struct lock_list *src_entry,
void *data,
- int (*match)(struct lock_list *entry, void *data),
+ bool (*match)(struct lock_list *entry, void *data),
struct lock_list **target_entry)
{
return __bfs(src_entry, data, match, target_entry,
@@ -1833,7 +1833,7 @@ print_circular_bug_header(struct lock_list *entry,
unsigned int depth,
print_circular_bug_entry(entry, depth);
}
-static inline int class_equal(struct lock_list *entry, void *data)
+static inline bool class_equal(struct lock_list *entry, void *data)
{
return entry->class == data;
}
@@ -1888,10 +1888,10 @@ static noinline void print_bfs_bug(int ret)
WARN(1, "lockdep bfs error:%d\n", ret);
}
-static int noop_count(struct lock_list *entry, void *data)
+static bool noop_count(struct lock_list *entry, void *data)
{
(*(unsigned long *)data)++;
- return 0;
+ return false;
}
static unsigned long __lockdep_count_forward_deps(struct lock_list *this)
@@ -2032,11 +2032,11 @@ check_redundant(struct held_lock *src, struct held_lock
*target)
#ifdef CONFIG_TRACE_IRQFLAGS
-static inline int usage_accumulate(struct lock_list *entry, void *mask)
+static inline bool usage_accumulate(struct lock_list *entry, void *mask)
{
*(unsigned long *)mask |= entry->class->usage_mask;
- return 0;
+ return false;
}
/*
@@ -2045,9 +2045,9 @@ static inline int usage_accumulate(struct lock_list
*entry, void *mask)
* without creating any illegal irq-safe -> irq-unsafe lock dependency.
*/
-static inline int usage_match(struct lock_list *entry, void *mask)
+static inline bool usage_match(struct lock_list *entry, void *mask)
{
- return entry->class->usage_mask & *(unsigned long *)mask;
+ return !!(entry->class->usage_mask & *(unsigned long *)mask);
}
/*
[tip: locking/core] Revert "locking/lockdep/selftests: Fix mixed read-write ABBA tests"
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 108dc42ed3507fe06214d51ab15fca7771df8bbd
Gitweb:
https://git.kernel.org/tip/108dc42ed3507fe06214d51ab15fca7771df8bbd
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:36 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:07 +02:00
Revert "locking/lockdep/selftests: Fix mixed read-write ABBA tests"
This reverts commit d82fed75294229abc9d757f08a4817febae6c4f4.
Since we now could handle mixed read-write deadlock detection well, the
self tests could be detected as expected, no need to use this
work-around.
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-18-boqun.f...@gmail.com
---
lib/locking-selftest.c | 8
1 file changed, 8 deletions(-)
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index 76c314a..4264cf4 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -2273,14 +2273,6 @@ void locking_selftest(void)
print_testname("mixed read-lock/lock-write ABBA");
pr_cont(" |");
dotest(rlock_ABBA1, FAILURE, LOCKTYPE_RWLOCK);
-#ifdef CONFIG_PROVE_LOCKING
- /*
-* Lockdep does indeed fail here, but there's nothing we can do about
-* that now. Don't kill lockdep for it.
-*/
- unexpected_testcase_failures--;
-#endif
-
pr_cont(" |");
dotest(rwsem_ABBA1, FAILURE, LOCKTYPE_RWSEM);
[tip: locking/core] locking/selftest: Add test cases for queued_read_lock()
The following commit has been merged into the locking/core branch of tip:
Commit-ID: ad56450db86413ff911eb527b5a49e04a4345e61
Gitweb:
https://git.kernel.org/tip/ad56450db86413ff911eb527b5a49e04a4345e61
Author:Boqun Feng
AuthorDate:Fri, 07 Aug 2020 15:42:37 +08:00
Committer: Peter Zijlstra
CommitterDate: Wed, 26 Aug 2020 12:42:07 +02:00
locking/selftest: Add test cases for queued_read_lock()
Add two self test cases for the following case:
P0: P1: P2:
spin_lock_irq() read_lock()
write_lock_irq()
read_lock() spin_lock()
, which is a deadlock, as the read_lock() on P0 cannot get the lock
because of the fairness.
P0: P1: P2:
spin_lock() read_lock()
write_lock()
read_lock() spin_lock_irq()
, which is not a deadlock, as the read_lock() on P0 can get the lock
because it could use the unfair fastpass.
Signed-off-by: Boqun Feng
Signed-off-by: Peter Zijlstra (Intel)
Link: https://lkml.kernel.org/r/20200807074238.1632519-19-boqun.f...@gmail.com
---
lib/locking-selftest.c | 104 -
1 file changed, 104 insertions(+)
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index 4264cf4..17f8f6f 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -2201,6 +2201,108 @@ static void ww_tests(void)
pr_cont("\n");
}
+
+/*
+ *
+ * read_lock();
+ *
+ * spin_lock();
+ * spin_lock();
+ * read_lock();
+ *
+ * is a deadlock.
+ */
+static void queued_read_lock_hardirq_RE_Er(void)
+{
+ HARDIRQ_ENTER();
+ read_lock(_A);
+ LOCK(B);
+ UNLOCK(B);
+ read_unlock(_A);
+ HARDIRQ_EXIT();
+
+ HARDIRQ_DISABLE();
+ LOCK(B);
+ read_lock(_A);
+ read_unlock(_A);
+ UNLOCK(B);
+ HARDIRQ_ENABLE();
+}
+
+/*
+ *
+ * spin_lock();
+ *
+ * read_lock();
+ * read_lock();
+ * spin_lock();
+ *
+ * is not a deadlock.
+ */
+static void queued_read_lock_hardirq_ER_rE(void)
+{
+ HARDIRQ_ENTER();
+ LOCK(B);
+ read_lock(_A);
+ read_unlock(_A);
+ UNLOCK(B);
+ HARDIRQ_EXIT();
+
+ HARDIRQ_DISABLE();
+ read_lock(_A);
+ LOCK(B);
+ UNLOCK(B);
+ read_unlock(_A);
+ HARDIRQ_ENABLE();
+}
+
+/*
+ *
+ * spin_lock();
+ * read_lock();
+ *
+ * spin_lock();
+ * read_lock();
+ *
+ * is a deadlock. Because the two read_lock()s are both non-recursive readers.
+ */
+static void queued_read_lock_hardirq_inversion(void)
+{
+
+ HARDIRQ_ENTER();
+ LOCK(B);
+ UNLOCK(B);
+ HARDIRQ_EXIT();
+
+ HARDIRQ_DISABLE();
+ LOCK(B);
+ read_lock(_A);
+ read_unlock(_A);
+ UNLOCK(B);
+ HARDIRQ_ENABLE();
+
+ read_lock(_A);
+ read_unlock(_A);
+}
+
+static void queued_read_lock_tests(void)
+{
+ printk("
--\n");
+ printk(" | queued read lock tests |\n");
+ printk(" ---\n");
+ print_testname("hardirq read-lock/lock-read");
+ dotest(queued_read_lock_hardirq_RE_Er, FAILURE, LOCKTYPE_RWLOCK);
+ pr_cont("\n");
+
+ print_testname("hardirq lock-read/read-lock");
+ dotest(queued_read_lock_hardirq_ER_rE, SUCCESS, LOCKTYPE_RWLOCK);
+ pr_cont("\n");
+
+ print_testname("hardirq inversion");
+ dotest(queued_read_lock_hardirq_inversion, FAILURE, LOCKTYPE_RWLOCK);
+ pr_cont("\n");
+}
+
void locking_selftest(void)
{
/*
@@ -2318,6 +2420,8 @@ void locking_selftest(void)
/*
* queued_read_lock() specific test cases can be put here
*/
+ if (IS_ENABLED(CONFIG_QUEUED_RWLOCKS))
+ queued_read_lock_tests();
if (unexpected_testcase_failures) {
printk("-\n");
