* [PATCH 0/6] Fix lockdep vs local_lock_t
@ 2020-12-10 14:42 Peter Zijlstra
2020-12-10 14:42 ` [PATCH 1/6] locking/selftests: More granular debug_locks_verbose Peter Zijlstra
` (5 more replies)
0 siblings, 6 replies; 8+ messages in thread
From: Peter Zijlstra @ 2020-12-10 14:42 UTC (permalink / raw)
To: mingo, will, boqun.feng; +Cc: linux-kernel, tglx, bigeasy, peterz
Hi,
After a few days of confusion, here are patches that (hopefully!) teach lockdep
about local_lock_t.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH 1/6] locking/selftests: More granular debug_locks_verbose
2020-12-10 14:42 [PATCH 0/6] Fix lockdep vs local_lock_t Peter Zijlstra
@ 2020-12-10 14:42 ` Peter Zijlstra
2020-12-10 14:42 ` [PATCH 2/6] locking/lockdep: Mark local_lock_t Peter Zijlstra
` (4 subsequent siblings)
5 siblings, 0 replies; 8+ messages in thread
From: Peter Zijlstra @ 2020-12-10 14:42 UTC (permalink / raw)
To: mingo, will, boqun.feng; +Cc: linux-kernel, tglx, bigeasy, peterz
Showing all tests all the time is tiresome.
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
Documentation/admin-guide/kernel-parameters.txt | 11 ++++++-----
lib/locking-selftest.c | 5 +++--
2 files changed, 9 insertions(+), 7 deletions(-)
--- a/Documentation/admin-guide/kernel-parameters.txt
+++ b/Documentation/admin-guide/kernel-parameters.txt
@@ -802,13 +802,14 @@
insecure, please do not use on production kernels.
debug_locks_verbose=
- [KNL] verbose self-tests
- Format=<0|1>
+ [KNL] verbose locking self-tests
+ Format: <int>
Print debugging info while doing the locking API
self-tests.
- We default to 0 (no extra messages), setting it to
- 1 will print _a lot_ more information - normally
- only useful to kernel developers.
+ Bitmask for the various LOCKTYPE_ tests. Defaults to 0
+ (no extra messages), setting it to -1 (all bits set)
+ will print _a_lot_ more information - normally only
+ useful to lockdep developers.
debug_objects [KNL] Enable object debugging
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -1390,6 +1390,8 @@ static void dotest(void (*testcase_fn)(v
WARN_ON(irqs_disabled());
+ debug_locks_silent = !(debug_locks_verbose & lockclass_mask);
+
testcase_fn();
/*
* Filter out expected failures:
@@ -1410,7 +1412,7 @@ static void dotest(void (*testcase_fn)(v
}
testcase_total++;
- if (debug_locks_verbose)
+ if (debug_locks_verbose & lockclass_mask)
pr_cont(" lockclass mask: %x, debug_locks: %d, expected: %d\n",
lockclass_mask, debug_locks, expected);
/*
@@ -2630,7 +2632,6 @@ void locking_selftest(void)
printk(" --------------------------------------------------------------------------\n");
init_shared_classes();
- debug_locks_silent = !debug_locks_verbose;
lockdep_set_selftest_task(current);
DO_TESTCASE_6R("A-A deadlock", AA);
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH 2/6] locking/lockdep: Mark local_lock_t
2020-12-10 14:42 [PATCH 0/6] Fix lockdep vs local_lock_t Peter Zijlstra
2020-12-10 14:42 ` [PATCH 1/6] locking/selftests: More granular debug_locks_verbose Peter Zijlstra
@ 2020-12-10 14:42 ` Peter Zijlstra
2020-12-10 14:42 ` [PATCH 3/6] locking/lockdep: Add a skip() function to __bfs() Peter Zijlstra
` (3 subsequent siblings)
5 siblings, 0 replies; 8+ messages in thread
From: Peter Zijlstra @ 2020-12-10 14:42 UTC (permalink / raw)
To: mingo, will, boqun.feng; +Cc: linux-kernel, tglx, bigeasy, peterz
The local_lock_t's are special, because they cannot form IRQ
inversions, make sure we can tell them apart from the rest of the
locks.
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
include/linux/local_lock_internal.h | 5 ++++-
include/linux/lockdep.h | 15 ++++++++++++---
include/linux/lockdep_types.h | 18 ++++++++++++++----
kernel/locking/lockdep.c | 16 +++++++++-------
4 files changed, 39 insertions(+), 15 deletions(-)
--- a/include/linux/local_lock_internal.h
+++ b/include/linux/local_lock_internal.h
@@ -18,6 +18,7 @@ typedef struct {
.dep_map = { \
.name = #lockname, \
.wait_type_inner = LD_WAIT_CONFIG, \
+ .lock_type = LD_LOCK_PERCPU, \
}
#else
# define LL_DEP_MAP_INIT(lockname)
@@ -30,7 +31,9 @@ do { \
static struct lock_class_key __key; \
\
debug_check_no_locks_freed((void *)lock, sizeof(*lock));\
- lockdep_init_map_wait(&(lock)->dep_map, #lock, &__key, 0, LD_WAIT_CONFIG);\
+ lockdep_init_map_type(&(lock)->dep_map, #lock, &__key, 0, \
+ LD_WAIT_CONFIG, LD_WAIT_INV, \
+ LD_LOCK_PERCPU); \
} while (0)
#ifdef CONFIG_DEBUG_LOCK_ALLOC
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -185,12 +185,19 @@ extern void lockdep_unregister_key(struc
* to lockdep:
*/
-extern void lockdep_init_map_waits(struct lockdep_map *lock, const char *name,
- struct lock_class_key *key, int subclass, short inner, short outer);
+extern void lockdep_init_map_type(struct lockdep_map *lock, const char *name,
+ struct lock_class_key *key, int subclass, u8 inner, u8 outer, u8 lock_type);
+
+static inline void
+lockdep_init_map_waits(struct lockdep_map *lock, const char *name,
+ struct lock_class_key *key, int subclass, u8 inner, u8 outer)
+{
+ lockdep_init_map_type(lock, name, key, subclass, inner, LD_WAIT_INV, LD_LOCK_NORMAL);
+}
static inline void
lockdep_init_map_wait(struct lockdep_map *lock, const char *name,
- struct lock_class_key *key, int subclass, short inner)
+ struct lock_class_key *key, int subclass, u8 inner)
{
lockdep_init_map_waits(lock, name, key, subclass, inner, LD_WAIT_INV);
}
@@ -340,6 +347,8 @@ static inline void lockdep_set_selftest_
# define lock_set_class(l, n, k, s, i) do { } while (0)
# define lock_set_subclass(l, s, i) do { } while (0)
# define lockdep_init() do { } while (0)
+# define lockdep_init_map_type(lock, name, key, sub, inner, outer) \
+ do { (void)(name); (void)(key); } while (0)
# define lockdep_init_map_waits(lock, name, key, sub, inner, outer) \
do { (void)(name); (void)(key); } while (0)
# define lockdep_init_map_wait(lock, name, key, sub, inner) \
--- a/include/linux/lockdep_types.h
+++ b/include/linux/lockdep_types.h
@@ -30,6 +30,12 @@ enum lockdep_wait_type {
LD_WAIT_MAX, /* must be last */
};
+enum lockdep_lock_type {
+ LD_LOCK_NORMAL = 0, /* normal, catch all */
+ LD_LOCK_PERCPU, /* percpu */
+ LD_LOCK_MAX,
+};
+
#ifdef CONFIG_LOCKDEP
/*
@@ -119,8 +125,10 @@ struct lock_class {
int name_version;
const char *name;
- short wait_type_inner;
- short wait_type_outer;
+ u8 wait_type_inner;
+ u8 wait_type_outer;
+ u8 lock_type;
+ /* u8 hole; */
#ifdef CONFIG_LOCK_STAT
unsigned long contention_point[LOCKSTAT_POINTS];
@@ -169,8 +177,10 @@ struct lockdep_map {
struct lock_class_key *key;
struct lock_class *class_cache[NR_LOCKDEP_CACHING_CLASSES];
const char *name;
- short wait_type_outer; /* can be taken in this context */
- short wait_type_inner; /* presents this context */
+ u8 wait_type_outer; /* can be taken in this context */
+ u8 wait_type_inner; /* presents this context */
+ u8 lock_type;
+ /* u8 hole; */
#ifdef CONFIG_LOCK_STAT
int cpu;
unsigned long ip;
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1290,6 +1290,7 @@ register_lock_class(struct lockdep_map *
class->name_version = count_matching_names(class);
class->wait_type_inner = lock->wait_type_inner;
class->wait_type_outer = lock->wait_type_outer;
+ class->lock_type = lock->lock_type;
/*
* We use RCU's safe list-add method to make
* parallel walking of the hash-list safe:
@@ -4503,9 +4504,9 @@ print_lock_invalid_wait_context(struct t
*/
static int check_wait_context(struct task_struct *curr, struct held_lock *next)
{
- short next_inner = hlock_class(next)->wait_type_inner;
- short next_outer = hlock_class(next)->wait_type_outer;
- short curr_inner;
+ u8 next_inner = hlock_class(next)->wait_type_inner;
+ u8 next_outer = hlock_class(next)->wait_type_outer;
+ u8 curr_inner;
int depth;
if (!next_inner || next->trylock)
@@ -4532,7 +4533,7 @@ static int check_wait_context(struct tas
for (; depth < curr->lockdep_depth; depth++) {
struct held_lock *prev = curr->held_locks + depth;
- short prev_inner = hlock_class(prev)->wait_type_inner;
+ u8 prev_inner = hlock_class(prev)->wait_type_inner;
if (prev_inner) {
/*
@@ -4581,9 +4582,9 @@ static inline int check_wait_context(str
/*
* Initialize a lock instance's lock-class mapping info:
*/
-void lockdep_init_map_waits(struct lockdep_map *lock, const char *name,
+void lockdep_init_map_type(struct lockdep_map *lock, const char *name,
struct lock_class_key *key, int subclass,
- short inner, short outer)
+ u8 inner, u8 outer, u8 lock_type)
{
int i;
@@ -4606,6 +4607,7 @@ void lockdep_init_map_waits(struct lockd
lock->wait_type_outer = outer;
lock->wait_type_inner = inner;
+ lock->lock_type = lock_type;
/*
* No key, no joy, we need to hash something.
@@ -4640,7 +4642,7 @@ void lockdep_init_map_waits(struct lockd
raw_local_irq_restore(flags);
}
}
-EXPORT_SYMBOL_GPL(lockdep_init_map_waits);
+EXPORT_SYMBOL_GPL(lockdep_init_map_type);
struct lock_class_key __lockdep_no_validate__;
EXPORT_SYMBOL_GPL(__lockdep_no_validate__);
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH 3/6] locking/lockdep: Add a skip() function to __bfs()
2020-12-10 14:42 [PATCH 0/6] Fix lockdep vs local_lock_t Peter Zijlstra
2020-12-10 14:42 ` [PATCH 1/6] locking/selftests: More granular debug_locks_verbose Peter Zijlstra
2020-12-10 14:42 ` [PATCH 2/6] locking/lockdep: Mark local_lock_t Peter Zijlstra
@ 2020-12-10 14:42 ` Peter Zijlstra
2020-12-10 14:42 ` [PATCH 4/6] locking/lockdep: Clean up check_redundant() a bit Peter Zijlstra
` (2 subsequent siblings)
5 siblings, 0 replies; 8+ messages in thread
From: Peter Zijlstra @ 2020-12-10 14:42 UTC (permalink / raw)
To: mingo, will, boqun.feng; +Cc: linux-kernel, tglx, bigeasy, peterz
From: Boqun Feng <boqun.feng@gmail.com>
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 <boqun.feng@gmail.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
kernel/locking/lockdep.c | 65 +++++++++++++++++++++++++++++++++++++++--------
1 file changed, 55 insertions(+), 10 deletions(-)
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1672,6 +1672,7 @@ static inline struct lock_list *__bfs_ne
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
/*
* 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_for
unsigned long count = 0;
struct lock_list *target_entry;
- __bfs_forwards(this, (void *)&count, noop_count, &target_entry);
+ __bfs_forwards(this, (void *)&count, noop_count, NULL, &target_entry);
return count;
}
@@ -2044,7 +2052,7 @@ static unsigned long __lockdep_count_bac
unsigned long count = 0;
struct lock_list *target_entry;
- __bfs_backwards(this, (void *)&count, noop_count, &target_entry);
+ __bfs_backwards(this, (void *)&count, noop_count, NULL, &target_entry);
return count;
}
@@ -2072,11 +2080,12 @@ unsigned long lockdep_count_backward_dep
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,
debug_atomic_inc(nr_cyclic_checks);
- ret = check_path(target, &src_entry, hlock_conflict, &target_entry);
+ ret = check_path(target, &src_entry, hlock_conflict, NULL, &target_entry);
if (unlikely(ret == BFS_RMATCH)) {
if (!*trace) {
@@ -2152,7 +2161,7 @@ check_redundant(struct held_lock *src, s
debug_atomic_inc(nr_redundant_checks);
- ret = check_path(target, &src_entry, hlock_equal, &target_entry);
+ ret = check_path(target, &src_entry, hlock_equal, NULL, &target_entry);
if (ret == BFS_RMATCH)
debug_atomic_inc(nr_redundant);
@@ -2246,7 +2291,7 @@ find_usage_forwards(struct lock_list *ro
debug_atomic_inc(nr_find_usage_forwards_checks);
- result = __bfs_forwards(root, &usage_mask, usage_match, target_entry);
+ result = __bfs_forwards(root, &usage_mask, usage_match, NULL, target_entry);
return result;
}
@@ -2263,7 +2308,7 @@ find_usage_backwards(struct lock_list *r
debug_atomic_inc(nr_find_usage_backwards_checks);
- result = __bfs_backwards(root, &usage_mask, usage_match, target_entry);
+ result = __bfs_backwards(root, &usage_mask, usage_match, NULL, target_entry);
return result;
}
@@ -2628,7 +2673,7 @@ static int check_irq_usage(struct task_s
*/
bfs_init_rootb(&this, prev);
- ret = __bfs_backwards(&this, &usage_mask, usage_accumulate, NULL);
+ ret = __bfs_backwards(&this, &usage_mask, usage_accumulate, NULL, NULL);
if (bfs_error(ret)) {
print_bfs_bug(ret);
return 0;
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH 4/6] locking/lockdep: Clean up check_redundant() a bit
2020-12-10 14:42 [PATCH 0/6] Fix lockdep vs local_lock_t Peter Zijlstra
` (2 preceding siblings ...)
2020-12-10 14:42 ` [PATCH 3/6] locking/lockdep: Add a skip() function to __bfs() Peter Zijlstra
@ 2020-12-10 14:42 ` Peter Zijlstra
2020-12-10 20:09 ` Qian Cai
2020-12-10 14:42 ` [PATCH 5/6] locking/lockdep: Exclude local_lock_t from IRQ inversions Peter Zijlstra
2020-12-10 14:43 ` [PATCH 6/6] locking/selftests: Add local_lock inversion tests Peter Zijlstra
5 siblings, 1 reply; 8+ messages in thread
From: Peter Zijlstra @ 2020-12-10 14:42 UTC (permalink / raw)
To: mingo, will, boqun.feng; +Cc: linux-kernel, tglx, bigeasy, peterz
In preparation for adding an TRACE_IRQFLAGS dependent skip function to
check_redundant(), move it below the TRACE_IRQFLAGS #ifdef.
While there, provide a stub function to reduce #ifdef usage.
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
kernel/locking/lockdep.c | 91 +++++++++++++++++++++++++----------------------
1 file changed, 49 insertions(+), 42 deletions(-)
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2130,46 +2130,6 @@ check_noncircular(struct held_lock *src,
return ret;
}
-#ifdef CONFIG_LOCKDEP_SMALL
-/*
- * Check that the dependency graph starting at <src> can lead to
- * <target> or not. If it can, <src> -> <target> dependency is already
- * in the graph.
- *
- * Return BFS_RMATCH if it does, or BFS_RMATCH if it does not, return BFS_E* if
- * any error appears in the bfs search.
- */
-static noinline enum bfs_result
-check_redundant(struct held_lock *src, struct held_lock *target)
-{
- enum bfs_result ret;
- struct lock_list *target_entry;
- struct lock_list src_entry;
-
- bfs_init_root(&src_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 <src> -> <target>. So if <src> 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 <prev> is S, we set initial ->only_xr to false
- * because both -(S*)-> (equal) and -(E*)-> (stronger) are redundant.
- */
- src_entry.only_xr = src->read == 0;
-
- debug_atomic_inc(nr_redundant_checks);
-
- ret = check_path(target, &src_entry, hlock_equal, NULL, &target_entry);
-
- if (ret == BFS_RMATCH)
- debug_atomic_inc(nr_redundant);
-
- return ret;
-}
-#endif
-
#ifdef CONFIG_TRACE_IRQFLAGS
/*
@@ -2706,6 +2666,55 @@ static inline int check_irq_usage(struct
}
#endif /* CONFIG_TRACE_IRQFLAGS */
+#ifdef CONFIG_LOCKDEP_SMALL
+/*
+ * Check that the dependency graph starting at <src> can lead to
+ * <target> or not. If it can, <src> -> <target> dependency is already
+ * in the graph.
+ *
+ * Return BFS_RMATCH if it does, or BFS_RMATCH if it does not, return BFS_E* if
+ * any error appears in the bfs search.
+ */
+static noinline enum bfs_result
+check_redundant(struct held_lock *src, struct held_lock *target)
+{
+ enum bfs_result ret;
+ struct lock_list *target_entry;
+ struct lock_list src_entry;
+
+ bfs_init_root(&src_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 <src> -> <target>. So if <src> 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 <prev> is S, we set initial ->only_xr to false
+ * because both -(S*)-> (equal) and -(E*)-> (stronger) are redundant.
+ */
+ src_entry.only_xr = src->read == 0;
+
+ debug_atomic_inc(nr_redundant_checks);
+
+ ret = check_path(target, &src_entry, hlock_equal, NULL, &target_entry);
+
+ if (ret == BFS_RMATCH)
+ debug_atomic_inc(nr_redundant);
+
+ return ret;
+}
+
+#else
+
+static inline enum bfs_result
+check_redundant(struct held_lock *src, struct held_lock *target)
+{
+ return BFS_RNOMATCH;
+}
+
+#endif
+
static void inc_chains(int irq_context)
{
if (irq_context & LOCK_CHAIN_HARDIRQ_CONTEXT)
@@ -2926,7 +2935,6 @@ check_prev_add(struct task_struct *curr,
}
}
-#ifdef CONFIG_LOCKDEP_SMALL
/*
* Is the <prev> -> <next> link redundant?
*/
@@ -2935,7 +2943,6 @@ check_prev_add(struct task_struct *curr,
return 0;
else if (ret == BFS_RMATCH)
return 2;
-#endif
if (!*trace) {
*trace = save_trace();
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH 5/6] locking/lockdep: Exclude local_lock_t from IRQ inversions
2020-12-10 14:42 [PATCH 0/6] Fix lockdep vs local_lock_t Peter Zijlstra
` (3 preceding siblings ...)
2020-12-10 14:42 ` [PATCH 4/6] locking/lockdep: Clean up check_redundant() a bit Peter Zijlstra
@ 2020-12-10 14:42 ` Peter Zijlstra
2020-12-10 14:43 ` [PATCH 6/6] locking/selftests: Add local_lock inversion tests Peter Zijlstra
5 siblings, 0 replies; 8+ messages in thread
From: Peter Zijlstra @ 2020-12-10 14:42 UTC (permalink / raw)
To: mingo, will, boqun.feng; +Cc: linux-kernel, tglx, bigeasy, peterz
From: Boqun Feng <boqun.feng@gmail.com>
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:
CPU0 CPU1
local_lock(B) spin_lock_irq(A)
<IRQ>
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 <boqun.feng@gmail.com>
[peterz: Changelog]
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
kernel/locking/lockdep.c | 57 +++++++++++++++++++++++++++++++++++++++++++----
1 file changed, 53 insertions(+), 4 deletions(-)
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2200,6 +2200,44 @@ static inline bool usage_match(struct lo
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);
+ * <interrupted>
+ * 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 *ro
debug_atomic_inc(nr_find_usage_forwards_checks);
- result = __bfs_forwards(root, &usage_mask, usage_match, NULL, target_entry);
+ result = __bfs_forwards(root, &usage_mask, usage_match, usage_skip, target_entry);
return result;
}
@@ -2232,7 +2270,7 @@ find_usage_backwards(struct lock_list *r
debug_atomic_inc(nr_find_usage_backwards_checks);
- result = __bfs_backwards(root, &usage_mask, usage_match, NULL, target_entry);
+ result = __bfs_backwards(root, &usage_mask, usage_match, usage_skip, target_entry);
return result;
}
@@ -2597,7 +2635,7 @@ static int check_irq_usage(struct task_s
*/
bfs_init_rootb(&this, prev);
- ret = __bfs_backwards(&this, &usage_mask, usage_accumulate, NULL, NULL);
+ ret = __bfs_backwards(&this, &usage_mask, usage_accumulate, usage_skip, NULL);
if (bfs_error(ret)) {
print_bfs_bug(ret);
return 0;
@@ -2664,6 +2702,12 @@ static inline int check_irq_usage(struct
{
return 1;
}
+
+static inline bool usage_skip(struct lock_list *entry, void *mask)
+{
+ return false;
+}
+
#endif /* CONFIG_TRACE_IRQFLAGS */
#ifdef CONFIG_LOCKDEP_SMALL
@@ -2697,7 +2741,12 @@ check_redundant(struct held_lock *src, s
debug_atomic_inc(nr_redundant_checks);
- ret = check_path(target, &src_entry, hlock_equal, NULL, &target_entry);
+ /*
+ * Note: we skip local_lock() for redundant check, because as the
+ * comment in usage_skip(), A -> local_lock() -> B and A -> B are not
+ * the same.
+ */
+ ret = check_path(target, &src_entry, hlock_equal, usage_skip, &target_entry);
if (ret == BFS_RMATCH)
debug_atomic_inc(nr_redundant);
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH 6/6] locking/selftests: Add local_lock inversion tests
2020-12-10 14:42 [PATCH 0/6] Fix lockdep vs local_lock_t Peter Zijlstra
` (4 preceding siblings ...)
2020-12-10 14:42 ` [PATCH 5/6] locking/lockdep: Exclude local_lock_t from IRQ inversions Peter Zijlstra
@ 2020-12-10 14:43 ` Peter Zijlstra
5 siblings, 0 replies; 8+ messages in thread
From: Peter Zijlstra @ 2020-12-10 14:43 UTC (permalink / raw)
To: mingo, will, boqun.feng; +Cc: linux-kernel, tglx, bigeasy, peterz
Test the local_lock_t inversion scenarios.
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
lib/locking-selftest.c | 97 +++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 97 insertions(+)
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -23,6 +23,7 @@
#include <linux/debug_locks.h>
#include <linux/irqflags.h>
#include <linux/rtmutex.h>
+#include <linux/local_lock.h>
/*
* Change this to 1 if you want to see the failure printouts:
@@ -50,6 +51,7 @@ __setup("debug_locks_verbose=", setup_de
#define LOCKTYPE_RWSEM 0x8
#define LOCKTYPE_WW 0x10
#define LOCKTYPE_RTMUTEX 0x20
+#define LOCKTYPE_LL 0x40
static struct ww_acquire_ctx t, t2;
static struct ww_mutex o, o2, o3;
@@ -135,6 +137,8 @@ static DEFINE_RT_MUTEX(rtmutex_Z2);
#endif
+static local_lock_t local_A = INIT_LOCAL_LOCK(local_A);
+
/*
* non-inlined runtime initializers, to let separate locks share
* the same lock-class:
@@ -1314,6 +1318,7 @@ GENERATE_PERMUTATIONS_3_EVENTS(irq_read_
# define I_MUTEX(x) lockdep_reset_lock(&mutex_##x.dep_map)
# define I_RWSEM(x) lockdep_reset_lock(&rwsem_##x.dep_map)
# define I_WW(x) lockdep_reset_lock(&x.dep_map)
+# define I_LOCAL_LOCK(x) lockdep_reset_lock(&local_##x.dep_map)
#ifdef CONFIG_RT_MUTEXES
# define I_RTMUTEX(x) lockdep_reset_lock(&rtmutex_##x.dep_map)
#endif
@@ -1324,6 +1329,7 @@ GENERATE_PERMUTATIONS_3_EVENTS(irq_read_
# define I_MUTEX(x)
# define I_RWSEM(x)
# define I_WW(x)
+# define I_LOCAL_LOCK(x)
#endif
#ifndef I_RTMUTEX
@@ -1364,11 +1370,15 @@ static void reset_locks(void)
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);
+ I_LOCAL_LOCK(A);
+
lockdep_reset();
+
I2(A); I2(B); I2(C); I2(D);
init_shared_classes();
raw_spin_lock_init(&raw_lock_A);
raw_spin_lock_init(&raw_lock_B);
+ local_lock_init(&local_A);
ww_mutex_init(&o, &ww_lockdep); ww_mutex_init(&o2, &ww_lockdep); ww_mutex_init(&o3, &ww_lockdep);
memset(&t, 0, sizeof(t)); memset(&t2, 0, sizeof(t2));
@@ -2605,6 +2615,91 @@ static void wait_context_tests(void)
pr_cont("\n");
}
+static void local_lock_2(void)
+{
+ local_lock_acquire(&local_A); /* IRQ-ON */
+ local_lock_release(&local_A);
+
+ HARDIRQ_ENTER();
+ spin_lock(&lock_A); /* IN-IRQ */
+ spin_unlock(&lock_A);
+ HARDIRQ_EXIT()
+
+ HARDIRQ_DISABLE();
+ spin_lock(&lock_A);
+ local_lock_acquire(&local_A); /* IN-IRQ <-> IRQ-ON cycle, false */
+ local_lock_release(&local_A);
+ spin_unlock(&lock_A);
+ HARDIRQ_ENABLE();
+}
+
+static void local_lock_3A(void)
+{
+ local_lock_acquire(&local_A); /* IRQ-ON */
+ spin_lock(&lock_B); /* IRQ-ON */
+ spin_unlock(&lock_B);
+ local_lock_release(&local_A);
+
+ HARDIRQ_ENTER();
+ spin_lock(&lock_A); /* IN-IRQ */
+ spin_unlock(&lock_A);
+ HARDIRQ_EXIT()
+
+ HARDIRQ_DISABLE();
+ spin_lock(&lock_A);
+ local_lock_acquire(&local_A); /* IN-IRQ <-> IRQ-ON cycle only if we count local_lock(), false */
+ local_lock_release(&local_A);
+ spin_unlock(&lock_A);
+ HARDIRQ_ENABLE();
+}
+
+static void local_lock_3B(void)
+{
+ local_lock_acquire(&local_A); /* IRQ-ON */
+ spin_lock(&lock_B); /* IRQ-ON */
+ spin_unlock(&lock_B);
+ local_lock_release(&local_A);
+
+ HARDIRQ_ENTER();
+ spin_lock(&lock_A); /* IN-IRQ */
+ spin_unlock(&lock_A);
+ HARDIRQ_EXIT()
+
+ HARDIRQ_DISABLE();
+ spin_lock(&lock_A);
+ local_lock_acquire(&local_A); /* IN-IRQ <-> IRQ-ON cycle only if we count local_lock(), false */
+ local_lock_release(&local_A);
+ spin_unlock(&lock_A);
+ HARDIRQ_ENABLE();
+
+ HARDIRQ_DISABLE();
+ spin_lock(&lock_A);
+ spin_lock(&lock_B); /* IN-IRQ <-> IRQ-ON cycle, true */
+ spin_unlock(&lock_B);
+ spin_unlock(&lock_A);
+ HARDIRQ_DISABLE();
+
+}
+
+static void local_lock_tests(void)
+{
+ printk(" --------------------------------------------------------------------------\n");
+ printk(" | local_lock tests |\n");
+ printk(" ---------------------\n");
+
+ print_testname("local_lock inversion 2");
+ dotest(local_lock_2, SUCCESS, LOCKTYPE_LL);
+ pr_cont("\n");
+
+ print_testname("local_lock inversion 3A");
+ dotest(local_lock_3A, SUCCESS, LOCKTYPE_LL);
+ pr_cont("\n");
+
+ print_testname("local_lock inversion 3B");
+ dotest(local_lock_3B, FAILURE, LOCKTYPE_LL);
+ pr_cont("\n");
+}
+
void locking_selftest(void)
{
/*
@@ -2729,6 +2824,8 @@ void locking_selftest(void)
if (IS_ENABLED(CONFIG_PROVE_RAW_LOCK_NESTING))
wait_context_tests();
+ local_lock_tests();
+
if (unexpected_testcase_failures) {
printk("-----------------------------------------------------------------\n");
debug_locks = 0;
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 4/6] locking/lockdep: Clean up check_redundant() a bit
2020-12-10 14:42 ` [PATCH 4/6] locking/lockdep: Clean up check_redundant() a bit Peter Zijlstra
@ 2020-12-10 20:09 ` Qian Cai
0 siblings, 0 replies; 8+ messages in thread
From: Qian Cai @ 2020-12-10 20:09 UTC (permalink / raw)
To: Peter Zijlstra, mingo, will, boqun.feng; +Cc: linux-kernel, tglx, bigeasy
On Thu, 2020-12-10 at 15:42 +0100, Peter Zijlstra wrote:
[]
> /*
> @@ -2706,6 +2666,55 @@ static inline int check_irq_usage(struct
> }
> #endif /* CONFIG_TRACE_IRQFLAGS */
>
> +#ifdef CONFIG_LOCKDEP_SMALL
> +/*
> + * Check that the dependency graph starting at <src> can lead to
> + * <target> or not. If it can, <src> -> <target> dependency is already
> + * in the graph.
> + *
> + * Return BFS_RMATCH if it does, or BFS_RMATCH if it does not, return BFS_E* if
> + * any error appears in the bfs search.
Correction -- or BFS_RNOMATCH if it does not.
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2020-12-10 20:12 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-12-10 14:42 [PATCH 0/6] Fix lockdep vs local_lock_t Peter Zijlstra
2020-12-10 14:42 ` [PATCH 1/6] locking/selftests: More granular debug_locks_verbose Peter Zijlstra
2020-12-10 14:42 ` [PATCH 2/6] locking/lockdep: Mark local_lock_t Peter Zijlstra
2020-12-10 14:42 ` [PATCH 3/6] locking/lockdep: Add a skip() function to __bfs() Peter Zijlstra
2020-12-10 14:42 ` [PATCH 4/6] locking/lockdep: Clean up check_redundant() a bit Peter Zijlstra
2020-12-10 20:09 ` Qian Cai
2020-12-10 14:42 ` [PATCH 5/6] locking/lockdep: Exclude local_lock_t from IRQ inversions Peter Zijlstra
2020-12-10 14:43 ` [PATCH 6/6] locking/selftests: Add local_lock inversion tests Peter Zijlstra
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).