This adds a method to tell lockdep not to check lock ordering within a
lock class - but to still check lock ordering w.r.t. other lock types.

This is for bcachefs, where for btree node locks we have our own
deadlock avoidance strategy w.r.t. other btree node locks (cycle
detection), but we still want lockdep to check lock ordering w.r.t.
other lock types.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Will Deacon <will@kernel.org>
Cc: Waiman Long <longman@redhat.com>
Cc: Boqun Feng <boqun.feng@gmail.com>
---
 include/linux/lockdep.h       |  6 ++++++
 include/linux/lockdep_types.h |  2 +-
 kernel/locking/lockdep.c      | 26 ++++++++++++++++++++++++++
 3 files changed, 33 insertions(+), 1 deletion(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index e858c288c7..f6cc8709e2 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -665,4 +665,10 @@ lockdep_rcu_suspicious(const char *file, const int line, const char *s)
 }
 #endif
 
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+void lockdep_set_no_check_recursion(struct lockdep_map *map);
+#else
+static inline void lockdep_set_no_check_recursion(struct lockdep_map *map) {}
+#endif
+
 #endif /* __LINUX_LOCKDEP_H */
diff --git a/include/linux/lockdep_types.h b/include/linux/lockdep_types.h
index d22430840b..506e769b4a 100644
--- a/include/linux/lockdep_types.h
+++ b/include/linux/lockdep_types.h
@@ -128,7 +128,7 @@ struct lock_class {
 	u8				wait_type_inner;
 	u8				wait_type_outer;
 	u8				lock_type;
-	/* u8				hole; */
+	u8				no_check_recursion;
 
 #ifdef CONFIG_LOCK_STAT
 	unsigned long			contention_point[LOCKSTAT_POINTS];
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index e631464070..f022b58dfa 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3024,6 +3024,9 @@ check_deadlock(struct task_struct *curr, struct held_lock *next)
 		if ((next->read == 2) && prev->read)
 			continue;
 
+		if (hlock_class(next)->no_check_recursion)
+			continue;
+
 		/*
 		 * We're holding the nest_lock, which serializes this lock's
 		 * nesting behaviour.
@@ -3085,6 +3088,10 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 		return 2;
 	}
 
+	if (hlock_class(prev) == hlock_class(next) &&
+	    hlock_class(prev)->no_check_recursion)
+		return 2;
+
 	/*
 	 * Prove that the new <prev> -> <next> dependency would not
 	 * create a circular dependency in the graph. (We do this by
@@ -6620,3 +6627,22 @@ void lockdep_rcu_suspicious(const char *file, const int line, const char *s)
 	warn_rcu_exit(rcu);
 }
 EXPORT_SYMBOL_GPL(lockdep_rcu_suspicious);
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+void lockdep_set_no_check_recursion(struct lockdep_map *lock)
+{
+	struct lock_class *class = lock->class_cache[0];
+	unsigned long flags;
+
+	raw_local_irq_save(flags);
+	lockdep_recursion_inc();
+
+	if (!class)
+		class = register_lock_class(lock, 0, 0);
+	if (class)
+		class->no_check_recursion = true;
+	lockdep_recursion_finish();
+	raw_local_irq_restore(flags);
+}
+EXPORT_SYMBOL_GPL(lockdep_set_no_check_recursion);
+#endif
-- 
2.40.1

On Tue, May 09, 2023 at 12:56:28PM -0400, Kent Overstreet wrote:
> This adds a method to tell lockdep not to check lock ordering within a
> lock class - but to still check lock ordering w.r.t. other lock types.
> 
> This is for bcachefs, where for btree node locks we have our own
> deadlock avoidance strategy w.r.t. other btree node locks (cycle
> detection), but we still want lockdep to check lock ordering w.r.t.
> other lock types.
> 

ISTR you had a much nicer version of this where you gave a custom order
function -- what happend to that?

On Tue, May 09, 2023 at 09:31:47PM +0200, Peter Zijlstra wrote:
> On Tue, May 09, 2023 at 12:56:28PM -0400, Kent Overstreet wrote:
> > This adds a method to tell lockdep not to check lock ordering within a
> > lock class - but to still check lock ordering w.r.t. other lock types.
> > 
> > This is for bcachefs, where for btree node locks we have our own
> > deadlock avoidance strategy w.r.t. other btree node locks (cycle
> > detection), but we still want lockdep to check lock ordering w.r.t.
> > other lock types.
> > 
> 
> ISTR you had a much nicer version of this where you gave a custom order
> function -- what happend to that?

Actually, I spoke too soon; this patch and the other series with the
comparison function solve different problems.

For bcachefs btree node locks, we don't have a defined lock ordering at
all - we do full runtime cycle detection, so we don't want lockdep
checking for self deadlock because we're handling that but we _do_ want
lockdep checking lock ordering of btree node locks w.r.t. other locks in
the system.

On Tue, May 09, 2023 at 04:18:59PM -0400, Kent Overstreet wrote:
> On Tue, May 09, 2023 at 09:31:47PM +0200, Peter Zijlstra wrote:
> > On Tue, May 09, 2023 at 12:56:28PM -0400, Kent Overstreet wrote:
> > > This adds a method to tell lockdep not to check lock ordering within a
> > > lock class - but to still check lock ordering w.r.t. other lock types.
> > > 
> > > This is for bcachefs, where for btree node locks we have our own
> > > deadlock avoidance strategy w.r.t. other btree node locks (cycle
> > > detection), but we still want lockdep to check lock ordering w.r.t.
> > > other lock types.
> > > 
> > 
> > ISTR you had a much nicer version of this where you gave a custom order
> > function -- what happend to that?
> 
> Actually, I spoke too soon; this patch and the other series with the
> comparison function solve different problems.
> 
> For bcachefs btree node locks, we don't have a defined lock ordering at
> all - we do full runtime cycle detection, so we don't want lockdep
> checking for self deadlock because we're handling that but we _do_ want
> lockdep checking lock ordering of btree node locks w.r.t. other locks in
> the system.

Have you read the ww_mutex code? If not, please do so, it does similar
things.

The way it gets around the self-nesting check is by using the nest_lock
annotation, the acquire context itself also has a dep_map for this
purpose.

On Wed, May 10, 2023 at 10:59:05AM +0200, Peter Zijlstra wrote:
> On Tue, May 09, 2023 at 04:18:59PM -0400, Kent Overstreet wrote:
> > On Tue, May 09, 2023 at 09:31:47PM +0200, Peter Zijlstra wrote:
> > > On Tue, May 09, 2023 at 12:56:28PM -0400, Kent Overstreet wrote:
> > > > This adds a method to tell lockdep not to check lock ordering within a
> > > > lock class - but to still check lock ordering w.r.t. other lock types.
> > > > 
> > > > This is for bcachefs, where for btree node locks we have our own
> > > > deadlock avoidance strategy w.r.t. other btree node locks (cycle
> > > > detection), but we still want lockdep to check lock ordering w.r.t.
> > > > other lock types.
> > > > 
> > > 
> > > ISTR you had a much nicer version of this where you gave a custom order
> > > function -- what happend to that?
> > 
> > Actually, I spoke too soon; this patch and the other series with the
> > comparison function solve different problems.
> > 
> > For bcachefs btree node locks, we don't have a defined lock ordering at
> > all - we do full runtime cycle detection, so we don't want lockdep
> > checking for self deadlock because we're handling that but we _do_ want
> > lockdep checking lock ordering of btree node locks w.r.t. other locks in
> > the system.
> 
> Have you read the ww_mutex code? If not, please do so, it does similar
> things.
> 
> The way it gets around the self-nesting check is by using the nest_lock
> annotation, the acquire context itself also has a dep_map for this
> purpose.

So, spent some time plumbing this through the six lock code and seeing
how it'd work.

I like it in theory, it's got the right semantics and it would allow for
lockdep to check that we're not taking locks with more than one
btree_trans in the same thread. Unfortunately, we've got code paths that
are meant to be called from contexts that may or may not have a
btree_trans - and this is fine right now, because they just use
trylock(), but having to plumb nest_lock through is going to make a mess
of things.

(The relevant codepaths include shrinker callbacks, where we definitely
can not just init a new btree_trans, and also the btree node write path
which can be kicked off from all sorts of places).

Can we go with lockdep_set_no_check_recursion() for now? It's a pretty
small addition to the lockdep code.

On Wed, May 10, 2023 at 10:59:05AM +0200, Peter Zijlstra wrote:
> On Tue, May 09, 2023 at 04:18:59PM -0400, Kent Overstreet wrote:
> > On Tue, May 09, 2023 at 09:31:47PM +0200, Peter Zijlstra wrote:
> > > On Tue, May 09, 2023 at 12:56:28PM -0400, Kent Overstreet wrote:
> > > > This adds a method to tell lockdep not to check lock ordering within a
> > > > lock class - but to still check lock ordering w.r.t. other lock types.
> > > > 
> > > > This is for bcachefs, where for btree node locks we have our own
> > > > deadlock avoidance strategy w.r.t. other btree node locks (cycle
> > > > detection), but we still want lockdep to check lock ordering w.r.t.
> > > > other lock types.
> > > > 
> > > 
> > > ISTR you had a much nicer version of this where you gave a custom order
> > > function -- what happend to that?
> > 
> > Actually, I spoke too soon; this patch and the other series with the
> > comparison function solve different problems.
> > 
> > For bcachefs btree node locks, we don't have a defined lock ordering at
> > all - we do full runtime cycle detection, so we don't want lockdep
> > checking for self deadlock because we're handling that but we _do_ want
> > lockdep checking lock ordering of btree node locks w.r.t. other locks in
> > the system.
> 
> Have you read the ww_mutex code? If not, please do so, it does similar
> things.
> 
> The way it gets around the self-nesting check is by using the nest_lock
> annotation, the acquire context itself also has a dep_map for this
> purpose.

This might work.

I was confused for a good bit when reading tho code to figure out how
it works - nest_lock seems to be a pretty bad name, it's really not a
lock. acquire_ctx?

On Wed, May 10, 2023 at 04:38:15PM -0400, Kent Overstreet wrote:
> On Wed, May 10, 2023 at 10:59:05AM +0200, Peter Zijlstra wrote:

> > Have you read the ww_mutex code? If not, please do so, it does similar
> > things.
> > 
> > The way it gets around the self-nesting check is by using the nest_lock
> > annotation, the acquire context itself also has a dep_map for this
> > purpose.
> 
> This might work.
> 
> I was confused for a good bit when reading tho code to figure out how
> it works - nest_lock seems to be a pretty bad name, it's really not a
> lock. acquire_ctx?

That's just how ww_mutex uses it, the annotation itself comes from
mm_take_all_locks() where mm->mmap_lock (the lock formerly known as
mmap_sem) is used to serialize multi acquisition of vma locks.

That is, no other code takes multiple vma locks (be it i_mmap_rwsem or
anonvma->root->rwsem) in any order. These locks nest inside mmap_lock
and therefore by holding mmap_lock you serialize the whole thing and can
take them in any order you like.

Perhaps, now, all these many years later another name would've made more
sense, but I don't think it's worth the hassle of the tree-wide rename
(there's a few other users since).

On Thu, May 11, 2023 at 10:25:44AM +0200, Peter Zijlstra wrote:
> On Wed, May 10, 2023 at 04:38:15PM -0400, Kent Overstreet wrote:
> > On Wed, May 10, 2023 at 10:59:05AM +0200, Peter Zijlstra wrote:
> 
> > > Have you read the ww_mutex code? If not, please do so, it does similar
> > > things.
> > > 
> > > The way it gets around the self-nesting check is by using the nest_lock
> > > annotation, the acquire context itself also has a dep_map for this
> > > purpose.
> > 
> > This might work.
> > 
> > I was confused for a good bit when reading tho code to figure out how
> > it works - nest_lock seems to be a pretty bad name, it's really not a
> > lock. acquire_ctx?
> 
> That's just how ww_mutex uses it, the annotation itself comes from
> mm_take_all_locks() where mm->mmap_lock (the lock formerly known as
> mmap_sem) is used to serialize multi acquisition of vma locks.
> 
> That is, no other code takes multiple vma locks (be it i_mmap_rwsem or
> anonvma->root->rwsem) in any order. These locks nest inside mmap_lock
> and therefore by holding mmap_lock you serialize the whole thing and can
> take them in any order you like.
> 
> Perhaps, now, all these many years later another name would've made more
> sense, but I don't think it's worth the hassle of the tree-wide rename
> (there's a few other users since).

Thanks for the history lesson :)

On 5/9/23 16:18, Kent Overstreet wrote:
> On Tue, May 09, 2023 at 09:31:47PM +0200, Peter Zijlstra wrote:
>> On Tue, May 09, 2023 at 12:56:28PM -0400, Kent Overstreet wrote:
>>> This adds a method to tell lockdep not to check lock ordering within a
>>> lock class - but to still check lock ordering w.r.t. other lock types.
>>>
>>> This is for bcachefs, where for btree node locks we have our own
>>> deadlock avoidance strategy w.r.t. other btree node locks (cycle
>>> detection), but we still want lockdep to check lock ordering w.r.t.
>>> other lock types.
>>>
>> ISTR you had a much nicer version of this where you gave a custom order
>> function -- what happend to that?
> Actually, I spoke too soon; this patch and the other series with the
> comparison function solve different problems.
>
> For bcachefs btree node locks, we don't have a defined lock ordering at
> all - we do full runtime cycle detection, so we don't want lockdep
> checking for self deadlock because we're handling that but we _do_ want
> lockdep checking lock ordering of btree node locks w.r.t. other locks in
> the system.

Maybe you can use lock_set_novalidate_class() instead.

Cheers,
Longman

On Tue, May 09, 2023 at 04:27:46PM -0400, Waiman Long wrote:
> 
> On 5/9/23 16:18, Kent Overstreet wrote:
> > On Tue, May 09, 2023 at 09:31:47PM +0200, Peter Zijlstra wrote:
> > > On Tue, May 09, 2023 at 12:56:28PM -0400, Kent Overstreet wrote:
> > > > This adds a method to tell lockdep not to check lock ordering within a
> > > > lock class - but to still check lock ordering w.r.t. other lock types.
> > > > 
> > > > This is for bcachefs, where for btree node locks we have our own
> > > > deadlock avoidance strategy w.r.t. other btree node locks (cycle
> > > > detection), but we still want lockdep to check lock ordering w.r.t.
> > > > other lock types.
> > > > 
> > > ISTR you had a much nicer version of this where you gave a custom order
> > > function -- what happend to that?
> > Actually, I spoke too soon; this patch and the other series with the
> > comparison function solve different problems.
> > 
> > For bcachefs btree node locks, we don't have a defined lock ordering at
> > all - we do full runtime cycle detection, so we don't want lockdep
> > checking for self deadlock because we're handling that but we _do_ want
> > lockdep checking lock ordering of btree node locks w.r.t. other locks in
> > the system.
> 
> Maybe you can use lock_set_novalidate_class() instead.

No, we want that to go away, this is the replacement.

On 5/9/23 16:35, Kent Overstreet wrote:
> On Tue, May 09, 2023 at 04:27:46PM -0400, Waiman Long wrote:
>> On 5/9/23 16:18, Kent Overstreet wrote:
>>> On Tue, May 09, 2023 at 09:31:47PM +0200, Peter Zijlstra wrote:
>>>> On Tue, May 09, 2023 at 12:56:28PM -0400, Kent Overstreet wrote:
>>>>> This adds a method to tell lockdep not to check lock ordering within a
>>>>> lock class - but to still check lock ordering w.r.t. other lock types.
>>>>>
>>>>> This is for bcachefs, where for btree node locks we have our own
>>>>> deadlock avoidance strategy w.r.t. other btree node locks (cycle
>>>>> detection), but we still want lockdep to check lock ordering w.r.t.
>>>>> other lock types.
>>>>>
>>>> ISTR you had a much nicer version of this where you gave a custom order
>>>> function -- what happend to that?
>>> Actually, I spoke too soon; this patch and the other series with the
>>> comparison function solve different problems.
>>>
>>> For bcachefs btree node locks, we don't have a defined lock ordering at
>>> all - we do full runtime cycle detection, so we don't want lockdep
>>> checking for self deadlock because we're handling that but we _do_ want
>>> lockdep checking lock ordering of btree node locks w.r.t. other locks in
>>> the system.
>> Maybe you can use lock_set_novalidate_class() instead.
> No, we want that to go away, this is the replacement.

OK, you can mention that in the commit log then.

Cheers,
Longman

On Tue, May 09, 2023 at 09:31:47PM +0200, Peter Zijlstra wrote:
> On Tue, May 09, 2023 at 12:56:28PM -0400, Kent Overstreet wrote:
> > This adds a method to tell lockdep not to check lock ordering within a
> > lock class - but to still check lock ordering w.r.t. other lock types.
> > 
> > This is for bcachefs, where for btree node locks we have our own
> > deadlock avoidance strategy w.r.t. other btree node locks (cycle
> > detection), but we still want lockdep to check lock ordering w.r.t.
> > other lock types.
> > 
> 
> ISTR you had a much nicer version of this where you gave a custom order
> function -- what happend to that?

Probably in the other branch that I was meaning to re-mail you separately,
clearly I hadn't pulled the latest versions back into here... expect
that shortly :)