Re: [RFC tip/locking/lockdep v5 08/17] lockdep: Fix recursive read lock related safe->unsafe detection
On Fri, Feb 23, 2018 at 04:58:12PM +0800, Boqun Feng wrote:
> Hmm... think again, maybe I can combine case 1 with 3, and case 2 with
> 4, because each of them could share the same find_usage_backwards(), and
> find_usage_forwards() uses a usage_match_forwards() as follow for the
> match function:
>
> static inline int usage_match_forwards(struct lock_list *entry, void
> *bit)
> {
> enum lock_usage_bit ub = (enum lock_usage_bit)bit;
> unsigned long mask;
> unsigned long read_mask;
>
> /* mask out the read bit */
> ub &= ~1;
>
> mask = 1ULL << ub;
> read_mask = 1ULL << (ub + 1);
>
> return (entry->class->usage_mask & mask) || // *-> L2 and L2
> is an irq-unsafe lock
> ((entry->class->usage_mask & read_mask) &&
> !entry->is_rr); // N-> L2 and L2 is an irq-read-unsafe lock
> }
>
> Got a bus to catch, I can explain this later, if you need ;-)
Right, that's about what I was thinking of. Clearly that needs a wee
comment but it's much better.
Re: [RFC tip/locking/lockdep v5 08/17] lockdep: Fix recursive read lock related safe->unsafe detection
On Fri, Feb 23, 2018 at 04:21:34PM +0800, Boqun Feng wrote:
> On Thu, Feb 22, 2018 at 06:46:54PM +0100, Peter Zijlstra wrote:
> > On Thu, Feb 22, 2018 at 03:08:55PM +0800, Boqun Feng wrote:
> > > There are four cases for recursive read lock realted deadlocks:
> > >
> > > (--(X..Y)--> means a strong dependency path starts with a --(X*)-->
> > > dependency and ends with a --(*Y)-- dependency.)
> > >
> > > 1.An irq-safe lock L1 has a dependency --(*..*)--> to an
> > > irq-unsafe lock L2.
> > >
> > > 2.An irq-read-safe lock L1 has a dependency --(N..*)--> to an
> > > irq-unsafe lock L2.
> > >
> > > 3.An irq-safe lock L1 has a dependency --(*..N)--> to an
> > > irq-read-unsafe lock L2.
> > >
> > > 4.An irq-read-safe lock L1 has a dependency --(N..N)--> to an
> > > irq-read-unsafe lock L2.
> > >
> > > The current check_usage() only checks 1) and 2), so this patch adds
> > > checks for 3) and 4) and makes sure when find_usage_{back,for}wards find
> > > an irq-read-{,un}safe lock, the traverse path should ends at a
> > > dependency --(*N)-->. Note when we search backwards, --(*N)--> indicates
> > > a real dependency --(N*)-->.
> >
> > This adds 4 __bfs() searches for every new link.
> >
> > Can't we make the existing traversals smarter?
>
> Haven't really thought this one through, I will try. But as you said, we
Hmm... think again, maybe I can combine case 1 with 3, and case 2 with
4, because each of them could share the same find_usage_backwards(), and
find_usage_forwards() uses a usage_match_forwards() as follow for the
match function:
static inline int usage_match_forwards(struct lock_list *entry, void
*bit)
{
enum lock_usage_bit ub = (enum lock_usage_bit)bit;
unsigned long mask;
unsigned long read_mask;
/* mask out the read bit */
ub &= ~1;
mask = 1ULL << ub;
read_mask = 1ULL << (ub + 1);
return (entry->class->usage_mask & mask) || // *-> L2 and L2
is an irq-unsafe lock
((entry->class->usage_mask & read_mask) &&
!entry->is_rr); // N-> L2 and L2 is an irq-read-unsafe lock
}
Got a bus to catch, I can explain this later, if you need ;-)
Regards,
Boqun
> only need to do more searchs for _new_ links, so I think it's the slow
> path, would the performance matter that much?
>
> Regards,
> Boqun
signature.asc
Description: PGP signature
Re: [RFC tip/locking/lockdep v5 08/17] lockdep: Fix recursive read lock related safe->unsafe detection
On Thu, Feb 22, 2018 at 06:46:54PM +0100, Peter Zijlstra wrote:
> On Thu, Feb 22, 2018 at 03:08:55PM +0800, Boqun Feng wrote:
> > There are four cases for recursive read lock realted deadlocks:
> >
> > (--(X..Y)--> means a strong dependency path starts with a --(X*)-->
> > dependency and ends with a --(*Y)-- dependency.)
> >
> > 1. An irq-safe lock L1 has a dependency --(*..*)--> to an
> > irq-unsafe lock L2.
> >
> > 2. An irq-read-safe lock L1 has a dependency --(N..*)--> to an
> > irq-unsafe lock L2.
> >
> > 3. An irq-safe lock L1 has a dependency --(*..N)--> to an
> > irq-read-unsafe lock L2.
> >
> > 4. An irq-read-safe lock L1 has a dependency --(N..N)--> to an
> > irq-read-unsafe lock L2.
> >
> > The current check_usage() only checks 1) and 2), so this patch adds
> > checks for 3) and 4) and makes sure when find_usage_{back,for}wards find
> > an irq-read-{,un}safe lock, the traverse path should ends at a
> > dependency --(*N)-->. Note when we search backwards, --(*N)--> indicates
> > a real dependency --(N*)-->.
>
> This adds 4 __bfs() searches for every new link.
>
> Can't we make the existing traversals smarter?
Haven't really thought this one through, I will try. But as you said, we
only need to do more searchs for _new_ links, so I think it's the slow
path, would the performance matter that much?
Regards,
Boqun
signature.asc
Description: PGP signature
Re: [RFC tip/locking/lockdep v5 08/17] lockdep: Fix recursive read lock related safe->unsafe detection
On Thu, Feb 22, 2018 at 03:08:55PM +0800, Boqun Feng wrote:
> There are four cases for recursive read lock realted deadlocks:
>
> (--(X..Y)--> means a strong dependency path starts with a --(X*)-->
> dependency and ends with a --(*Y)-- dependency.)
>
> 1.An irq-safe lock L1 has a dependency --(*..*)--> to an
> irq-unsafe lock L2.
>
> 2.An irq-read-safe lock L1 has a dependency --(N..*)--> to an
> irq-unsafe lock L2.
>
> 3.An irq-safe lock L1 has a dependency --(*..N)--> to an
> irq-read-unsafe lock L2.
>
> 4.An irq-read-safe lock L1 has a dependency --(N..N)--> to an
> irq-read-unsafe lock L2.
>
> The current check_usage() only checks 1) and 2), so this patch adds
> checks for 3) and 4) and makes sure when find_usage_{back,for}wards find
> an irq-read-{,un}safe lock, the traverse path should ends at a
> dependency --(*N)-->. Note when we search backwards, --(*N)--> indicates
> a real dependency --(N*)-->.
This adds 4 __bfs() searches for every new link.
Can't we make the existing traversals smarter?
Re: [RFC tip/locking/lockdep v5 08/17] lockdep: Fix recursive read lock related safe->unsafe detection
On Thu, Feb 22, 2018 at 03:08:55PM +0800, Boqun Feng wrote:
> There are four cases for recursive read lock realted deadlocks:
>
> (--(X..Y)--> means a strong dependency path starts with a --(X*)-->
> dependency and ends with a --(*Y)-- dependency.)
>
> 1.An irq-safe lock L1 has a dependency --(*..*)--> to an
> irq-unsafe lock L2.
>
> 2.An irq-read-safe lock L1 has a dependency --(N..*)--> to an
> irq-unsafe lock L2.
>
> 3.An irq-safe lock L1 has a dependency --(*..N)--> to an
> irq-read-unsafe lock L2.
>
> 4.An irq-read-safe lock L1 has a dependency --(N..N)--> to an
> irq-read-unsafe lock L2.
>
> The current check_usage() only checks 1) and 2), so this patch adds
> checks for 3) and 4) and makes sure when find_usage_{back,for}wards find
> an irq-read-{,un}safe lock, the traverse path should ends at a
> dependency --(*N)-->. Note when we search backwards, --(*N)--> indicates
> a real dependency --(N*)-->.
>
> Signed-off-by: Boqun Feng
> ---
> kernel/locking/lockdep.c | 17 -
> 1 file changed, 16 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 0b0ad3db78b4..bd3eef664f9d 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -1504,7 +1504,14 @@ check_redundant(struct lock_list *root, struct
> held_lock *target,
>
> static inline int usage_match(struct lock_list *entry, void *bit)
> {
> - return entry->class->usage_mask & (1 << (enum lock_usage_bit)bit);
> + enum lock_usage_bit ub = (enum lock_usage_bit)bit;
> +
> +
> + if (ub & 1)
> + return entry->class->usage_mask & (1 << ub) &&
> +!entry->is_rr;
> + else
> + return entry->class->usage_mask & (1 << ub);
> }
The whole is_rr/have_xr thing and backwards hurts my brain. That really
wants more than a little 'Note'.
Also, the above is unreadable, something like:
unsigned long usage_mask = entry->class->usage_mask;
enum lock_usage_bit ub = (enum lock_usage_bit)bit;
unsigned long mask = 1ULL << ub;
if (ub & 1) /* __STATE_RR */
return !entry->have_xr && (usage_mask & mask);
return !!(usage_mask & mask);
maybe. Also, perhaps we should make __bfs(.match) have a bool return
value.
[RFC tip/locking/lockdep v5 08/17] lockdep: Fix recursive read lock related safe->unsafe detection
There are four cases for recursive read lock realted deadlocks:
(--(X..Y)--> means a strong dependency path starts with a --(X*)-->
dependency and ends with a --(*Y)-- dependency.)
1. An irq-safe lock L1 has a dependency --(*..*)--> to an
irq-unsafe lock L2.
2. An irq-read-safe lock L1 has a dependency --(N..*)--> to an
irq-unsafe lock L2.
3. An irq-safe lock L1 has a dependency --(*..N)--> to an
irq-read-unsafe lock L2.
4. An irq-read-safe lock L1 has a dependency --(N..N)--> to an
irq-read-unsafe lock L2.
The current check_usage() only checks 1) and 2), so this patch adds
checks for 3) and 4) and makes sure when find_usage_{back,for}wards find
an irq-read-{,un}safe lock, the traverse path should ends at a
dependency --(*N)-->. Note when we search backwards, --(*N)--> indicates
a real dependency --(N*)-->.
Signed-off-by: Boqun Feng
---
kernel/locking/lockdep.c | 17 -
1 file changed, 16 insertions(+), 1 deletion(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 0b0ad3db78b4..bd3eef664f9d 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1504,7 +1504,14 @@ check_redundant(struct lock_list *root, struct held_lock
*target,
static inline int usage_match(struct lock_list *entry, void *bit)
{
- return entry->class->usage_mask & (1 << (enum lock_usage_bit)bit);
+ enum lock_usage_bit ub = (enum lock_usage_bit)bit;
+
+
+ if (ub & 1)
+ return entry->class->usage_mask & (1 << ub) &&
+ !entry->is_rr;
+ else
+ return entry->class->usage_mask & (1 << ub);
}
@@ -1815,6 +1822,10 @@ static int check_irq_usage(struct task_struct *curr,
struct held_lock *prev,
exclusive_bit(bit), state_name(bit)))
return 0;
+ if (!check_usage(curr, prev, next, bit,
+ exclusive_bit(bit) + 1, state_name(bit)))
+ return 0;
+
bit++; /* _READ */
/*
@@ -1827,6 +1838,10 @@ static int check_irq_usage(struct task_struct *curr,
struct held_lock *prev,
exclusive_bit(bit), state_name(bit)))
return 0;
+ if (!check_usage(curr, prev, next, bit,
+ exclusive_bit(bit) + 1, state_name(bit)))
+ return 0;
+
return 1;
}
--
2.16.1
