LKML Archive on lore.kernel.org
 help / color / Atom feed
* [PATCH] lockdep: Introduce CONFIG_LOCKDEP_LARGE
@ 2020-07-25  1:30 Tetsuo Handa
  2020-07-25  4:48 ` Dmitry Vyukov
  2020-08-27 15:20 ` [PATCH v2] lockdep: Allow tuning tracing capacity constants Tetsuo Handa
  0 siblings, 2 replies; 17+ messages in thread
From: Tetsuo Handa @ 2020-07-25  1:30 UTC (permalink / raw)
  To: Peter Zijlstra, Ingo Molnar, Will Deacon
  Cc: linux-kernel, Dmitry Vyukov, Tetsuo Handa, syzbot, syzbot, syzbot

Since syzkaller continues various test cases until the kernel crashes,
syzkaller tends to examine more locking dependencies than normal systems.
As a result, syzbot is reporting that the fuzz testing was terminated
due to hitting upper limits lockdep can track [1] [2] [3].

Like CONFIG_LOCKDEP_SMALL which halves the upper limits, let's introduce
CONFIG_LOCKDEP_LARGE which doubles the upper limits.

[1] https://syzkaller.appspot.com/bug?id=3d97ba93fb3566000c1c59691ea427370d33ea1b
[2] https://syzkaller.appspot.com/bug?id=381cb436fe60dc03d7fd2a092b46d7f09542a72a
[3] https://syzkaller.appspot.com/bug?id=a588183ac34c1437fc0785e8f220e88282e5a29f

Reported-by: syzbot <syzbot+cd0ec5211ac07c18c049@syzkaller.appspotmail.com>
Reported-by: syzbot <syzbot+91fd909b6e62ebe06131@syzkaller.appspotmail.com>
Reported-by: syzbot <syzbot+62ebe501c1ce9a91f68c@syzkaller.appspotmail.com>
Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
---
 kernel/locking/lockdep.c           | 4 ++++
 kernel/locking/lockdep_internals.h | 5 +++++
 lib/Kconfig.debug                  | 8 ++++++++
 3 files changed, 17 insertions(+)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 29a8de4..85ba7eb 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1349,7 +1349,11 @@ static int add_lock_to_list(struct lock_class *this,
 /*
  * For good efficiency of modular, we use power of 2
  */
+#ifdef CONFIG_LOCKDEP_LARGE
+#define MAX_CIRCULAR_QUEUE_SIZE		8192UL
+#else
 #define MAX_CIRCULAR_QUEUE_SIZE		4096UL
+#endif
 #define CQ_MASK				(MAX_CIRCULAR_QUEUE_SIZE-1)
 
 /*
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index baca699..00a3ec3 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -93,6 +93,11 @@ enum {
 #define MAX_LOCKDEP_CHAINS_BITS	15
 #define MAX_STACK_TRACE_ENTRIES	262144UL
 #define STACK_TRACE_HASH_SIZE	8192
+#elif defined(CONFIG_LOCKDEP_LARGE)
+#define MAX_LOCKDEP_ENTRIES	65536UL
+#define MAX_LOCKDEP_CHAINS_BITS	17
+#define MAX_STACK_TRACE_ENTRIES	1048576UL
+#define STACK_TRACE_HASH_SIZE	32768
 #else
 #define MAX_LOCKDEP_ENTRIES	32768UL
 
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 9ad9210..69ba624 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1266,6 +1266,14 @@ config LOCKDEP
 config LOCKDEP_SMALL
 	bool
 
+config LOCKDEP_LARGE
+	bool "Use larger buffer for tracking more locking dependencies"
+	depends on LOCKDEP && !LOCKDEP_SMALL
+	help
+	  If you say Y here, the upper limits the lock dependency engine uses will
+	  be doubled. Useful for fuzz testing which tends to test many complecated
+	  dependencies than normal systems.
+
 config DEBUG_LOCKDEP
 	bool "Lock dependency engine debugging"
 	depends on DEBUG_KERNEL && LOCKDEP
-- 
1.8.3.1


^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH] lockdep: Introduce CONFIG_LOCKDEP_LARGE
  2020-07-25  1:30 [PATCH] lockdep: Introduce CONFIG_LOCKDEP_LARGE Tetsuo Handa
@ 2020-07-25  4:48 ` Dmitry Vyukov
  2020-07-25  5:23   ` Tetsuo Handa
  2020-08-27 15:20 ` [PATCH v2] lockdep: Allow tuning tracing capacity constants Tetsuo Handa
  1 sibling, 1 reply; 17+ messages in thread
From: Dmitry Vyukov @ 2020-07-25  4:48 UTC (permalink / raw)
  To: Tetsuo Handa
  Cc: Peter Zijlstra, Ingo Molnar, Will Deacon, LKML, syzbot, syzbot, syzbot

On Sat, Jul 25, 2020 at 3:30 AM Tetsuo Handa
<penguin-kernel@i-love.sakura.ne.jp> wrote:
>
> Since syzkaller continues various test cases until the kernel crashes,
> syzkaller tends to examine more locking dependencies than normal systems.
> As a result, syzbot is reporting that the fuzz testing was terminated
> due to hitting upper limits lockdep can track [1] [2] [3].
>
> Like CONFIG_LOCKDEP_SMALL which halves the upper limits, let's introduce
> CONFIG_LOCKDEP_LARGE which doubles the upper limits.
>
> [1] https://syzkaller.appspot.com/bug?id=3d97ba93fb3566000c1c59691ea427370d33ea1b
> [2] https://syzkaller.appspot.com/bug?id=381cb436fe60dc03d7fd2a092b46d7f09542a72a
> [3] https://syzkaller.appspot.com/bug?id=a588183ac34c1437fc0785e8f220e88282e5a29f
>
> Reported-by: syzbot <syzbot+cd0ec5211ac07c18c049@syzkaller.appspotmail.com>
> Reported-by: syzbot <syzbot+91fd909b6e62ebe06131@syzkaller.appspotmail.com>
> Reported-by: syzbot <syzbot+62ebe501c1ce9a91f68c@syzkaller.appspotmail.com>
> Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
> ---
>  kernel/locking/lockdep.c           | 4 ++++
>  kernel/locking/lockdep_internals.h | 5 +++++
>  lib/Kconfig.debug                  | 8 ++++++++
>  3 files changed, 17 insertions(+)
>
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 29a8de4..85ba7eb 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -1349,7 +1349,11 @@ static int add_lock_to_list(struct lock_class *this,
>  /*
>   * For good efficiency of modular, we use power of 2
>   */
> +#ifdef CONFIG_LOCKDEP_LARGE
> +#define MAX_CIRCULAR_QUEUE_SIZE                8192UL
> +#else
>  #define MAX_CIRCULAR_QUEUE_SIZE                4096UL

Maybe this number should be the config value? So that we don't ever
return here to introduce "VERY_LARGE" :)
Also somebody may use it to _reduce_ size of the table for a smaller kernel.

> +#endif
>  #define CQ_MASK                                (MAX_CIRCULAR_QUEUE_SIZE-1)
>
>  /*
> diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
> index baca699..00a3ec3 100644
> --- a/kernel/locking/lockdep_internals.h
> +++ b/kernel/locking/lockdep_internals.h
> @@ -93,6 +93,11 @@ enum {
>  #define MAX_LOCKDEP_CHAINS_BITS        15
>  #define MAX_STACK_TRACE_ENTRIES        262144UL
>  #define STACK_TRACE_HASH_SIZE  8192
> +#elif defined(CONFIG_LOCKDEP_LARGE)
> +#define MAX_LOCKDEP_ENTRIES    65536UL
> +#define MAX_LOCKDEP_CHAINS_BITS        17
> +#define MAX_STACK_TRACE_ENTRIES        1048576UL
> +#define STACK_TRACE_HASH_SIZE  32768
>  #else
>  #define MAX_LOCKDEP_ENTRIES    32768UL
>
> diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
> index 9ad9210..69ba624 100644
> --- a/lib/Kconfig.debug
> +++ b/lib/Kconfig.debug
> @@ -1266,6 +1266,14 @@ config LOCKDEP
>  config LOCKDEP_SMALL
>         bool
>
> +config LOCKDEP_LARGE
> +       bool "Use larger buffer for tracking more locking dependencies"
> +       depends on LOCKDEP && !LOCKDEP_SMALL
> +       help
> +         If you say Y here, the upper limits the lock dependency engine uses will
> +         be doubled. Useful for fuzz testing which tends to test many complecated
> +         dependencies than normal systems.
> +
>  config DEBUG_LOCKDEP
>         bool "Lock dependency engine debugging"
>         depends on DEBUG_KERNEL && LOCKDEP
> --
> 1.8.3.1
>

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH] lockdep: Introduce CONFIG_LOCKDEP_LARGE
  2020-07-25  4:48 ` Dmitry Vyukov
@ 2020-07-25  5:23   ` Tetsuo Handa
  2020-08-04  2:36     ` Tetsuo Handa
  0 siblings, 1 reply; 17+ messages in thread
From: Tetsuo Handa @ 2020-07-25  5:23 UTC (permalink / raw)
  To: Dmitry Vyukov
  Cc: Peter Zijlstra, Ingo Molnar, Will Deacon, LKML, syzbot, syzbot, syzbot

On 2020/07/25 13:48, Dmitry Vyukov wrote:
>> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
>> index 29a8de4..85ba7eb 100644
>> --- a/kernel/locking/lockdep.c
>> +++ b/kernel/locking/lockdep.c
>> @@ -1349,7 +1349,11 @@ static int add_lock_to_list(struct lock_class *this,
>>  /*
>>   * For good efficiency of modular, we use power of 2
>>   */
>> +#ifdef CONFIG_LOCKDEP_LARGE
>> +#define MAX_CIRCULAR_QUEUE_SIZE                8192UL
>> +#else
>>  #define MAX_CIRCULAR_QUEUE_SIZE                4096UL
> 
> Maybe this number should be the config value? So that we don't ever
> return here to introduce "VERY_LARGE" :)

They can be "tiny, small, medium, compact, large and huge". Yeah, it's a joke. :-)

> Also somebody may use it to _reduce_ size of the table for a smaller kernel.

Maybe. But my feeling is that it is very rare that the kernel actually deadlocks
as soon as lockdep warned the possibility of deadlock.

Since syzbot runs many instances in parallel, a lot of CPU resource is spent for
checking the same dependency tree. However, the possibility of deadlock can be
warned for only locks held within each kernel boot, and it is impossible to hold
all locks with one kernel boot.

Then, it might be nice if lockdep can audit only "which lock was held from which
context and what backtrace" and export that log like KCOV data (instead of evaluating
the possibility of deadlock), and rebuild the whole dependency (and evaluate the
possibility of deadlock) across multiple kernel boots in userspace.

> 
>> +#endif
>>  #define CQ_MASK                                (MAX_CIRCULAR_QUEUE_SIZE-1)


^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH] lockdep: Introduce CONFIG_LOCKDEP_LARGE
  2020-07-25  5:23   ` Tetsuo Handa
@ 2020-08-04  2:36     ` Tetsuo Handa
  2020-08-18  9:57       ` Dmitry Vyukov
  0 siblings, 1 reply; 17+ messages in thread
From: Tetsuo Handa @ 2020-08-04  2:36 UTC (permalink / raw)
  To: Peter Zijlstra, Ingo Molnar, Will Deacon; +Cc: Dmitry Vyukov, LKML

Hello, Peter, Ingo and Will.

(Q1) Can we change the capacity using kernel config?

(Q2) If we can change the capacity, is it OK to specify these constants
     independently? (In other words, is there inter-dependency among
     these constants?)

(Q3) Do you think that we can extend lockdep to be used as a tool for auditing
     locks held in kernel space and rebuilding lock dependency map in user space?

On 2020/07/25 14:23, Tetsuo Handa wrote:
>> Also somebody may use it to _reduce_ size of the table for a smaller kernel.
> 
> Maybe. But my feeling is that it is very rare that the kernel actually deadlocks
> as soon as lockdep warned the possibility of deadlock.
> 
> Since syzbot runs many instances in parallel, a lot of CPU resource is spent for
> checking the same dependency tree. However, the possibility of deadlock can be
> warned for only locks held within each kernel boot, and it is impossible to hold
> all locks with one kernel boot.
> 
> Then, it might be nice if lockdep can audit only "which lock was held from which
> context and what backtrace" and export that log like KCOV data (instead of evaluating
> the possibility of deadlock), and rebuild the whole dependency (and evaluate the
> possibility of deadlock) across multiple kernel boots in userspace.


^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH] lockdep: Introduce CONFIG_LOCKDEP_LARGE
  2020-08-04  2:36     ` Tetsuo Handa
@ 2020-08-18  9:57       ` Dmitry Vyukov
  2020-08-18 11:07         ` Tetsuo Handa
  0 siblings, 1 reply; 17+ messages in thread
From: Dmitry Vyukov @ 2020-08-18  9:57 UTC (permalink / raw)
  To: Tetsuo Handa; +Cc: Peter Zijlstra, Ingo Molnar, Will Deacon, LKML

On Tue, Aug 4, 2020 at 4:36 AM Tetsuo Handa
<penguin-kernel@i-love.sakura.ne.jp> wrote:
>
> Hello, Peter, Ingo and Will.
>
> (Q1) Can we change the capacity using kernel config?
>
> (Q2) If we can change the capacity, is it OK to specify these constants
>      independently? (In other words, is there inter-dependency among
>      these constants?)


I think we should do this.
syzbot uses a very beefy kernel config and very broad load.
We are hitting "BUG: MAX_LOCKDEP_ENTRIES too low!" for the part 428
days and already hit it 96K times. It's just harming overall kernel
testing:
https://syzkaller.appspot.com/bug?id=3d97ba93fb3566000c1c59691ea427370d33ea1b

I think it's better if exact values are not hardcoded, but rather
specified in the config. Today we are switching from 4K to 8K, but as
we enable more configs and learn to reach more code, we may need 16K.


> (Q3) Do you think that we can extend lockdep to be used as a tool for auditing
>      locks held in kernel space and rebuilding lock dependency map in user space?

This looks like lots of work. Also unpleasant dependencies on
user-space. If there is a user-space component, it will need to be
deployed to _all_ of kernel testing systems and for all users of
syzkaller. And it will also be a dependency for reproducers. Currently
one can run a C reproducer and get the errors message from LOCKDEP. It
seems that a user-space component will make it significantly more
complicated.


> On 2020/07/25 14:23, Tetsuo Handa wrote:
> >> Also somebody may use it to _reduce_ size of the table for a smaller kernel.
> >
> > Maybe. But my feeling is that it is very rare that the kernel actually deadlocks
> > as soon as lockdep warned the possibility of deadlock.
> >
> > Since syzbot runs many instances in parallel, a lot of CPU resource is spent for
> > checking the same dependency tree. However, the possibility of deadlock can be
> > warned for only locks held within each kernel boot, and it is impossible to hold
> > all locks with one kernel boot.
> >
> > Then, it might be nice if lockdep can audit only "which lock was held from which
> > context and what backtrace" and export that log like KCOV data (instead of evaluating
> > the possibility of deadlock), and rebuild the whole dependency (and evaluate the
> > possibility of deadlock) across multiple kernel boots in userspace.
>

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH] lockdep: Introduce CONFIG_LOCKDEP_LARGE
  2020-08-18  9:57       ` Dmitry Vyukov
@ 2020-08-18 11:07         ` Tetsuo Handa
  2020-08-18 12:02           ` Dmitry Vyukov
  0 siblings, 1 reply; 17+ messages in thread
From: Tetsuo Handa @ 2020-08-18 11:07 UTC (permalink / raw)
  To: Dmitry Vyukov; +Cc: Peter Zijlstra, Ingo Molnar, Will Deacon, LKML

On 2020/08/18 18:57, Dmitry Vyukov wrote:
> On Tue, Aug 4, 2020 at 4:36 AM Tetsuo Handa
> <penguin-kernel@i-love.sakura.ne.jp> wrote:
>>
>> Hello, Peter, Ingo and Will.
>>
>> (Q1) Can we change the capacity using kernel config?
>>
>> (Q2) If we can change the capacity, is it OK to specify these constants
>>      independently? (In other words, is there inter-dependency among
>>      these constants?)
> 
> 
> I think we should do this.
> syzbot uses a very beefy kernel config and very broad load.
> We are hitting "BUG: MAX_LOCKDEP_ENTRIES too low!" for the part 428
> days and already hit it 96K times. It's just harming overall kernel
> testing:
> https://syzkaller.appspot.com/bug?id=3d97ba93fb3566000c1c59691ea427370d33ea1b
> 
> I think it's better if exact values are not hardcoded, but rather
> specified in the config. Today we are switching from 4K to 8K, but as
> we enable more configs and learn to reach more code, we may need 16K.

For short term, increasing the capacity would be fine. But for long term, I doubt.

Learning more locks being held within one boot by enabling more configs, I suspect
that it becomes more and more timing dependent and difficult to hold all locks that
can generate a lockdep warning.

> 
> 
>> (Q3) Do you think that we can extend lockdep to be used as a tool for auditing
>>      locks held in kernel space and rebuilding lock dependency map in user space?
> 
> This looks like lots of work. Also unpleasant dependencies on
> user-space. If there is a user-space component, it will need to be
> deployed to _all_ of kernel testing systems and for all users of
> syzkaller. And it will also be a dependency for reproducers. Currently
> one can run a C reproducer and get the errors message from LOCKDEP. It
> seems that a user-space component will make it significantly more
> complicated.

My suggestion is to detach lockdep warning from realtime alarming.

Since not all locks are always held (e.g. some locks are held only if exceeding
some threshold), requiring all locks being held within one boot sounds difficult.
Such requirement results in flaky bisection like "Fix bisection: failed" in
https://syzkaller.appspot.com/bug?id=b23ec126241ad0d86628de6eb5c1cff57d282632 .

Then, I'm wishing that we could build non-realtime alarming based on all locks held
across all boots on each vmlinux file.

> 
> 
>> On 2020/07/25 14:23, Tetsuo Handa wrote:
>>>> Also somebody may use it to _reduce_ size of the table for a smaller kernel.
>>>
>>> Maybe. But my feeling is that it is very rare that the kernel actually deadlocks
>>> as soon as lockdep warned the possibility of deadlock.
>>>
>>> Since syzbot runs many instances in parallel, a lot of CPU resource is spent for
>>> checking the same dependency tree. However, the possibility of deadlock can be
>>> warned for only locks held within each kernel boot, and it is impossible to hold
>>> all locks with one kernel boot.
>>>
>>> Then, it might be nice if lockdep can audit only "which lock was held from which
>>> context and what backtrace" and export that log like KCOV data (instead of evaluating
>>> the possibility of deadlock), and rebuild the whole dependency (and evaluate the
>>> possibility of deadlock) across multiple kernel boots in userspace.
>>


^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH] lockdep: Introduce CONFIG_LOCKDEP_LARGE
  2020-08-18 11:07         ` Tetsuo Handa
@ 2020-08-18 12:02           ` Dmitry Vyukov
  2020-08-18 12:59             ` Tetsuo Handa
  0 siblings, 1 reply; 17+ messages in thread
From: Dmitry Vyukov @ 2020-08-18 12:02 UTC (permalink / raw)
  To: Tetsuo Handa; +Cc: Peter Zijlstra, Ingo Molnar, Will Deacon, LKML, syzkaller

On Tue, Aug 18, 2020 at 1:07 PM Tetsuo Handa
<penguin-kernel@i-love.sakura.ne.jp> wrote:
>
> On 2020/08/18 18:57, Dmitry Vyukov wrote:
> > On Tue, Aug 4, 2020 at 4:36 AM Tetsuo Handa
> > <penguin-kernel@i-love.sakura.ne.jp> wrote:
> >>
> >> Hello, Peter, Ingo and Will.
> >>
> >> (Q1) Can we change the capacity using kernel config?
> >>
> >> (Q2) If we can change the capacity, is it OK to specify these constants
> >>      independently? (In other words, is there inter-dependency among
> >>      these constants?)
> >
> >
> > I think we should do this.
> > syzbot uses a very beefy kernel config and very broad load.
> > We are hitting "BUG: MAX_LOCKDEP_ENTRIES too low!" for the part 428
> > days and already hit it 96K times. It's just harming overall kernel
> > testing:
> > https://syzkaller.appspot.com/bug?id=3d97ba93fb3566000c1c59691ea427370d33ea1b
> >
> > I think it's better if exact values are not hardcoded, but rather
> > specified in the config. Today we are switching from 4K to 8K, but as
> > we enable more configs and learn to reach more code, we may need 16K.
>
> For short term, increasing the capacity would be fine. But for long term, I doubt.
>
> Learning more locks being held within one boot by enabling more configs, I suspect
> that it becomes more and more timing dependent and difficult to hold all locks that
> can generate a lockdep warning.
>
> >
> >
> >> (Q3) Do you think that we can extend lockdep to be used as a tool for auditing
> >>      locks held in kernel space and rebuilding lock dependency map in user space?
> >
> > This looks like lots of work. Also unpleasant dependencies on
> > user-space. If there is a user-space component, it will need to be
> > deployed to _all_ of kernel testing systems and for all users of
> > syzkaller. And it will also be a dependency for reproducers. Currently
> > one can run a C reproducer and get the errors message from LOCKDEP. It
> > seems that a user-space component will make it significantly more
> > complicated.
>
> My suggestion is to detach lockdep warning from realtime alarming.
>
> Since not all locks are always held (e.g. some locks are held only if exceeding
> some threshold), requiring all locks being held within one boot sounds difficult.
> Such requirement results in flaky bisection like "Fix bisection: failed" in
> https://syzkaller.appspot.com/bug?id=b23ec126241ad0d86628de6eb5c1cff57d282632 .
>
> Then, I'm wishing that we could build non-realtime alarming based on all locks held
> across all boots on each vmlinux file.

Unless I am missing something, deployment/maintenance story for this
for syzbot, syzkaller users, other kernel testing, reproducer
extraction, bisection, resproducer hermeticity is quite complicated. I
don't see it outweighing any potential benefit in reporting quality.

I also don't see how it will improve reproducer/bisection quality: to
confirm presence of a bug we still need to trigger all cycle edges
within a single run anyway, it does not have to be a single VM, but
still needs to be a single test case. And this "having all edges
within a single test case" seems to be the root problem. I don't see
how this proposal addresses this problem.

> >> On 2020/07/25 14:23, Tetsuo Handa wrote:
> >>>> Also somebody may use it to _reduce_ size of the table for a smaller kernel.
> >>>
> >>> Maybe. But my feeling is that it is very rare that the kernel actually deadlocks
> >>> as soon as lockdep warned the possibility of deadlock.
> >>>
> >>> Since syzbot runs many instances in parallel, a lot of CPU resource is spent for
> >>> checking the same dependency tree. However, the possibility of deadlock can be
> >>> warned for only locks held within each kernel boot, and it is impossible to hold
> >>> all locks with one kernel boot.
> >>>
> >>> Then, it might be nice if lockdep can audit only "which lock was held from which
> >>> context and what backtrace" and export that log like KCOV data (instead of evaluating
> >>> the possibility of deadlock), and rebuild the whole dependency (and evaluate the
> >>> possibility of deadlock) across multiple kernel boots in userspace.
> >>
>

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH] lockdep: Introduce CONFIG_LOCKDEP_LARGE
  2020-08-18 12:02           ` Dmitry Vyukov
@ 2020-08-18 12:59             ` Tetsuo Handa
  0 siblings, 0 replies; 17+ messages in thread
From: Tetsuo Handa @ 2020-08-18 12:59 UTC (permalink / raw)
  To: Dmitry Vyukov; +Cc: Peter Zijlstra, Ingo Molnar, Will Deacon, LKML, syzkaller

Peter, Ingo and Will. Would you answer (Q1) and (Q2)?

On 2020/08/18 21:02, Dmitry Vyukov wrote:
> On Tue, Aug 18, 2020 at 1:07 PM Tetsuo Handa
> <penguin-kernel@i-love.sakura.ne.jp> wrote:
>>
>> On 2020/08/18 18:57, Dmitry Vyukov wrote:
>>> On Tue, Aug 4, 2020 at 4:36 AM Tetsuo Handa
>>> <penguin-kernel@i-love.sakura.ne.jp> wrote:
>>>>
>>>> Hello, Peter, Ingo and Will.
>>>>
>>>> (Q1) Can we change the capacity using kernel config?
>>>>
>>>> (Q2) If we can change the capacity, is it OK to specify these constants
>>>>      independently? (In other words, is there inter-dependency among
>>>>      these constants?)
>>>
>>>
>>> I think we should do this.
>>> syzbot uses a very beefy kernel config and very broad load.
>>> We are hitting "BUG: MAX_LOCKDEP_ENTRIES too low!" for the part 428
>>> days and already hit it 96K times. It's just harming overall kernel
>>> testing:
>>> https://syzkaller.appspot.com/bug?id=3d97ba93fb3566000c1c59691ea427370d33ea1b
>>>
>>> I think it's better if exact values are not hardcoded, but rather
>>> specified in the config. Today we are switching from 4K to 8K, but as
>>> we enable more configs and learn to reach more code, we may need 16K.
>>
>> For short term, increasing the capacity would be fine. But for long term, I doubt.
>>
>> Learning more locks being held within one boot by enabling more configs, I suspect
>> that it becomes more and more timing dependent and difficult to hold all locks that
>> can generate a lockdep warning.
>>
>>>
>>>
>>>> (Q3) Do you think that we can extend lockdep to be used as a tool for auditing
>>>>      locks held in kernel space and rebuilding lock dependency map in user space?
>>>
>>> This looks like lots of work. Also unpleasant dependencies on
>>> user-space. If there is a user-space component, it will need to be
>>> deployed to _all_ of kernel testing systems and for all users of
>>> syzkaller. And it will also be a dependency for reproducers. Currently
>>> one can run a C reproducer and get the errors message from LOCKDEP. It
>>> seems that a user-space component will make it significantly more
>>> complicated.
>>
>> My suggestion is to detach lockdep warning from realtime alarming.
>>
>> Since not all locks are always held (e.g. some locks are held only if exceeding
>> some threshold), requiring all locks being held within one boot sounds difficult.
>> Such requirement results in flaky bisection like "Fix bisection: failed" in
>> https://syzkaller.appspot.com/bug?id=b23ec126241ad0d86628de6eb5c1cff57d282632 .
>>
>> Then, I'm wishing that we could build non-realtime alarming based on all locks held
>> across all boots on each vmlinux file.
> 
> Unless I am missing something, deployment/maintenance story for this
> for syzbot, syzkaller users, other kernel testing, reproducer
> extraction, bisection, resproducer hermeticity is quite complicated. I
> don't see it outweighing any potential benefit in reporting quality.

What I'm imaging is: do not try to judge lock dependency problems within
syzkaller (or other kernel testing) kernels. That is, no reproducer for
lock dependency problems, no bisection for lock dependency problems.
Utilize their resources for gathering only, and create lock dependency
(like kcov data) in some dedicated userspace component.

> 
> I also don't see how it will improve reproducer/bisection quality: to
> confirm presence of a bug we still need to trigger all cycle edges
> within a single run anyway, it does not have to be a single VM, but
> still needs to be a single test case. And this "having all edges
> within a single test case" seems to be the root problem. I don't see
> how this proposal addresses this problem.
> 
>>>> On 2020/07/25 14:23, Tetsuo Handa wrote:
>>>>>> Also somebody may use it to _reduce_ size of the table for a smaller kernel.
>>>>>
>>>>> Maybe. But my feeling is that it is very rare that the kernel actually deadlocks
>>>>> as soon as lockdep warned the possibility of deadlock.
>>>>>
>>>>> Since syzbot runs many instances in parallel, a lot of CPU resource is spent for
>>>>> checking the same dependency tree. However, the possibility of deadlock can be
>>>>> warned for only locks held within each kernel boot, and it is impossible to hold
>>>>> all locks with one kernel boot.
>>>>>
>>>>> Then, it might be nice if lockdep can audit only "which lock was held from which
>>>>> context and what backtrace" and export that log like KCOV data (instead of evaluating
>>>>> the possibility of deadlock), and rebuild the whole dependency (and evaluate the
>>>>> possibility of deadlock) across multiple kernel boots in userspace.
>>>>
>>


^ permalink raw reply	[flat|nested] 17+ messages in thread

* [PATCH v2] lockdep: Allow tuning tracing capacity constants.
  2020-07-25  1:30 [PATCH] lockdep: Introduce CONFIG_LOCKDEP_LARGE Tetsuo Handa
  2020-07-25  4:48 ` Dmitry Vyukov
@ 2020-08-27 15:20 ` Tetsuo Handa
  2020-09-04 16:05   ` Tetsuo Handa
  2020-10-10 12:58   ` [PATCH v3] " Tetsuo Handa
  1 sibling, 2 replies; 17+ messages in thread
From: Tetsuo Handa @ 2020-08-27 15:20 UTC (permalink / raw)
  To: Peter Zijlstra, Ingo Molnar, Will Deacon, Andrew Morton
  Cc: linux-kernel, Dmitry Vyukov, syzbot, syzbot, syzbot

Since syzkaller continues various test cases until the kernel crashes,
syzkaller tends to examine more locking dependencies than normal systems.
As a result, syzbot is reporting that the fuzz testing was terminated
due to hitting upper limits lockdep can track [1] [2] [3].

Let's allow individually tuning upper limits via kernel config options
(based on an assumption that there is no inter-dependency among these
constants).

[1] https://syzkaller.appspot.com/bug?id=3d97ba93fb3566000c1c59691ea427370d33ea1b
[2] https://syzkaller.appspot.com/bug?id=381cb436fe60dc03d7fd2a092b46d7f09542a72a
[3] https://syzkaller.appspot.com/bug?id=a588183ac34c1437fc0785e8f220e88282e5a29f

Reported-by: syzbot <syzbot+cd0ec5211ac07c18c049@syzkaller.appspotmail.com>
Reported-by: syzbot <syzbot+91fd909b6e62ebe06131@syzkaller.appspotmail.com>
Reported-by: syzbot <syzbot+62ebe501c1ce9a91f68c@syzkaller.appspotmail.com>
Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
---
 kernel/locking/lockdep.c           |  2 +-
 kernel/locking/lockdep_internals.h |  8 +++---
 lib/Kconfig.debug                  | 40 ++++++++++++++++++++++++++++++
 3 files changed, 45 insertions(+), 5 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 2fad21d345b0..5a058fcec435 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1349,7 +1349,7 @@ static int add_lock_to_list(struct lock_class *this,
 /*
  * For good efficiency of modular, we use power of 2
  */
-#define MAX_CIRCULAR_QUEUE_SIZE		4096UL
+#define MAX_CIRCULAR_QUEUE_SIZE		(1UL << CONFIG_LOCKDEP_CIRCULAR_QUEUE_BITS)
 #define CQ_MASK				(MAX_CIRCULAR_QUEUE_SIZE-1)
 
 /*
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index baca699b94e9..8435a11bf456 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -94,16 +94,16 @@ static const unsigned long LOCKF_USED_IN_IRQ_READ =
 #define MAX_STACK_TRACE_ENTRIES	262144UL
 #define STACK_TRACE_HASH_SIZE	8192
 #else
-#define MAX_LOCKDEP_ENTRIES	32768UL
+#define MAX_LOCKDEP_ENTRIES	(1UL << CONFIG_LOCKDEP_BITS)
 
-#define MAX_LOCKDEP_CHAINS_BITS	16
+#define MAX_LOCKDEP_CHAINS_BITS	CONFIG_LOCKDEP_CHAINS_BITS
 
 /*
  * Stack-trace: tightly packed array of stack backtrace
  * addresses. Protected by the hash_lock.
  */
-#define MAX_STACK_TRACE_ENTRIES	524288UL
-#define STACK_TRACE_HASH_SIZE	16384
+#define MAX_STACK_TRACE_ENTRIES	(1UL << CONFIG_LOCKDEP_STACK_TRACE_BITS)
+#define STACK_TRACE_HASH_SIZE	(1 << CONFIG_LOCKDEP_STACK_TRACE_HASH_BITS)
 #endif
 
 /*
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index e068c3c7189a..d7612e132986 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1311,6 +1311,46 @@ config LOCKDEP
 config LOCKDEP_SMALL
 	bool
 
+config LOCKDEP_BITS
+	int "Bitsize for MAX_LOCKDEP_ENTRIES"
+	depends on LOCKDEP && !LOCKDEP_SMALL
+	range 10 30
+	default 15
+	help
+	  Try increasing this value if you hit "BUG: MAX_LOCKDEP_ENTRIES too low!" message.
+
+config LOCKDEP_CHAINS_BITS
+	int "Bitsize for MAX_LOCKDEP_CHAINS"
+	depends on LOCKDEP && !LOCKDEP_SMALL
+	range 10 30
+	default 16
+	help
+	  Try increasing this value if you hit "BUG: MAX_LOCKDEP_CHAINS too low!" message.
+
+config LOCKDEP_STACK_TRACE_BITS
+	int "Bitsize for MAX_STACK_TRACE_ENTRIES"
+	depends on LOCKDEP && !LOCKDEP_SMALL
+	range 10 30
+	default 19
+	help
+	  Try increasing this value if you hit "BUG: MAX_STACK_TRACE_ENTRIES too low!" message.
+
+config LOCKDEP_STACK_TRACE_HASH_BITS
+	int "Bitsize for STACK_TRACE_HASH_SIZE"
+	depends on LOCKDEP && !LOCKDEP_SMALL
+	range 10 30
+	default 14
+	help
+	  Try increasing this value if you need large MAX_STACK_TRACE_ENTRIES.
+
+config LOCKDEP_CIRCULAR_QUEUE_BITS
+	int "Bitsize for elements in circular_queue struct"
+	depends on LOCKDEP
+	range 10 30
+	default 12
+	help
+	  Try increasing this value if you hit "lockdep bfs error:-1" warning due to __cq_enqueue() failure.
+
 config DEBUG_LOCKDEP
 	bool "Lock dependency engine debugging"
 	depends on DEBUG_KERNEL && LOCKDEP
-- 
2.18.4



^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v2] lockdep: Allow tuning tracing capacity constants.
  2020-08-27 15:20 ` [PATCH v2] lockdep: Allow tuning tracing capacity constants Tetsuo Handa
@ 2020-09-04 16:05   ` Tetsuo Handa
  2020-09-16 11:28     ` Dmitry Vyukov
  2020-10-10 12:58   ` [PATCH v3] " Tetsuo Handa
  1 sibling, 1 reply; 17+ messages in thread
From: Tetsuo Handa @ 2020-09-04 16:05 UTC (permalink / raw)
  To: Peter Zijlstra, Ingo Molnar, Will Deacon, Andrew Morton
  Cc: linux-kernel, Dmitry Vyukov

Hello. Can we apply this patch?

This patch addresses top crashers for syzbot, and applying this patch
will help utilizing syzbot's resource for finding other bugs.

On 2020/08/28 0:20, Tetsuo Handa wrote:
> Since syzkaller continues various test cases until the kernel crashes,
> syzkaller tends to examine more locking dependencies than normal systems.
> As a result, syzbot is reporting that the fuzz testing was terminated
> due to hitting upper limits lockdep can track [1] [2] [3].
> 
> Let's allow individually tuning upper limits via kernel config options
> (based on an assumption that there is no inter-dependency among these
> constants).
> 
> [1] https://syzkaller.appspot.com/bug?id=3d97ba93fb3566000c1c59691ea427370d33ea1b
> [2] https://syzkaller.appspot.com/bug?id=381cb436fe60dc03d7fd2a092b46d7f09542a72a
> [3] https://syzkaller.appspot.com/bug?id=a588183ac34c1437fc0785e8f220e88282e5a29f
> 
> Reported-by: syzbot <syzbot+cd0ec5211ac07c18c049@syzkaller.appspotmail.com>
> Reported-by: syzbot <syzbot+91fd909b6e62ebe06131@syzkaller.appspotmail.com>
> Reported-by: syzbot <syzbot+62ebe501c1ce9a91f68c@syzkaller.appspotmail.com>
> Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
> ---
>  kernel/locking/lockdep.c           |  2 +-
>  kernel/locking/lockdep_internals.h |  8 +++---
>  lib/Kconfig.debug                  | 40 ++++++++++++++++++++++++++++++
>  3 files changed, 45 insertions(+), 5 deletions(-)
> 

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v2] lockdep: Allow tuning tracing capacity constants.
  2020-09-04 16:05   ` Tetsuo Handa
@ 2020-09-16 11:28     ` Dmitry Vyukov
  2020-09-16 11:50       ` peterz
  0 siblings, 1 reply; 17+ messages in thread
From: Dmitry Vyukov @ 2020-09-16 11:28 UTC (permalink / raw)
  To: Tetsuo Handa
  Cc: Peter Zijlstra, Ingo Molnar, Will Deacon, Andrew Morton, LKML, syzkaller

On Fri, Sep 4, 2020 at 6:05 PM Tetsuo Handa
<penguin-kernel@i-love.sakura.ne.jp> wrote:
>
> Hello. Can we apply this patch?
>
> This patch addresses top crashers for syzbot, and applying this patch
> will help utilizing syzbot's resource for finding other bugs.

Acked-by: Dmitry Vyukov <dvyukov@google.com>

Peter, do you still have concerns with this?

Both MAX_LOCKDEP_ENTRIES and MAX_LOCKDEP_CHAINS still fire on syzbot a
lot and harm ability to test whole kernel:
https://syzkaller.appspot.com/bug?id=3d97ba93fb3566000c1c59691ea427370d33ea1b
https://syzkaller.appspot.com/bug?id=63fc8d0501c39609dd2f268e4190ec9a72619563

I hate disabling lockdep entirely as it also finds lots of useful things.


> On 2020/08/28 0:20, Tetsuo Handa wrote:
> > Since syzkaller continues various test cases until the kernel crashes,
> > syzkaller tends to examine more locking dependencies than normal systems.
> > As a result, syzbot is reporting that the fuzz testing was terminated
> > due to hitting upper limits lockdep can track [1] [2] [3].
> >
> > Let's allow individually tuning upper limits via kernel config options
> > (based on an assumption that there is no inter-dependency among these
> > constants).
> >
> > [1] https://syzkaller.appspot.com/bug?id=3d97ba93fb3566000c1c59691ea427370d33ea1b
> > [2] https://syzkaller.appspot.com/bug?id=381cb436fe60dc03d7fd2a092b46d7f09542a72a
> > [3] https://syzkaller.appspot.com/bug?id=a588183ac34c1437fc0785e8f220e88282e5a29f
> >
> > Reported-by: syzbot <syzbot+cd0ec5211ac07c18c049@syzkaller.appspotmail.com>
> > Reported-by: syzbot <syzbot+91fd909b6e62ebe06131@syzkaller.appspotmail.com>
> > Reported-by: syzbot <syzbot+62ebe501c1ce9a91f68c@syzkaller.appspotmail.com>
> > Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
> > ---
> >  kernel/locking/lockdep.c           |  2 +-
> >  kernel/locking/lockdep_internals.h |  8 +++---
> >  lib/Kconfig.debug                  | 40 ++++++++++++++++++++++++++++++
> >  3 files changed, 45 insertions(+), 5 deletions(-)
> >

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v2] lockdep: Allow tuning tracing capacity constants.
  2020-09-16 11:28     ` Dmitry Vyukov
@ 2020-09-16 11:50       ` peterz
  2020-09-16 12:14         ` Dmitry Vyukov
  0 siblings, 1 reply; 17+ messages in thread
From: peterz @ 2020-09-16 11:50 UTC (permalink / raw)
  To: Dmitry Vyukov
  Cc: Tetsuo Handa, Ingo Molnar, Will Deacon, Andrew Morton, LKML, syzkaller

On Wed, Sep 16, 2020 at 01:28:19PM +0200, Dmitry Vyukov wrote:
> On Fri, Sep 4, 2020 at 6:05 PM Tetsuo Handa
> <penguin-kernel@i-love.sakura.ne.jp> wrote:
> >
> > Hello. Can we apply this patch?
> >
> > This patch addresses top crashers for syzbot, and applying this patch
> > will help utilizing syzbot's resource for finding other bugs.
> 
> Acked-by: Dmitry Vyukov <dvyukov@google.com>
> 
> Peter, do you still have concerns with this?

Yeah, I still hate it with a passion; it discourages thinking. A bad
annotation that blows up the lockdep storage, no worries, we'll just
increase this :/

IIRC the issue with syzbot is that the current sysfs annotation is
pretty terrible and generates a gazillion classes, and syzbot likes
poking at /sys a lot and thus floods the system.

I don't know enough about sysfs to suggest an alternative, and haven't
exactly had spare time to look into it either :/

Examples of bad annotations is getting every CPU a separate class, that
leads to nr_cpus! chains if CPUs arbitrarily nest (nr_cpus^2 if there's
only a single nesting level).

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v2] lockdep: Allow tuning tracing capacity constants.
  2020-09-16 11:50       ` peterz
@ 2020-09-16 12:14         ` Dmitry Vyukov
  2020-09-28  0:24           ` Tetsuo Handa
  0 siblings, 1 reply; 17+ messages in thread
From: Dmitry Vyukov @ 2020-09-16 12:14 UTC (permalink / raw)
  To: Peter Zijlstra
  Cc: Tetsuo Handa, Ingo Molnar, Will Deacon, Andrew Morton, LKML, syzkaller

On Wed, Sep 16, 2020 at 1:51 PM <peterz@infradead.org> wrote:
>
> On Wed, Sep 16, 2020 at 01:28:19PM +0200, Dmitry Vyukov wrote:
> > On Fri, Sep 4, 2020 at 6:05 PM Tetsuo Handa
> > <penguin-kernel@i-love.sakura.ne.jp> wrote:
> > >
> > > Hello. Can we apply this patch?
> > >
> > > This patch addresses top crashers for syzbot, and applying this patch
> > > will help utilizing syzbot's resource for finding other bugs.
> >
> > Acked-by: Dmitry Vyukov <dvyukov@google.com>
> >
> > Peter, do you still have concerns with this?
>
> Yeah, I still hate it with a passion; it discourages thinking. A bad
> annotation that blows up the lockdep storage, no worries, we'll just
> increase this :/
>
> IIRC the issue with syzbot is that the current sysfs annotation is
> pretty terrible and generates a gazillion classes, and syzbot likes
> poking at /sys a lot and thus floods the system.
>
> I don't know enough about sysfs to suggest an alternative, and haven't
> exactly had spare time to look into it either :/
>
> Examples of bad annotations is getting every CPU a separate class, that
> leads to nr_cpus! chains if CPUs arbitrarily nest (nr_cpus^2 if there's
> only a single nesting level).

Maybe on "BUG: MAX_LOCKDEP_CHAINS too low!" we should then aggregate,
sort and show existing chains so that it's possible to identify if
there are any worst offenders and who they are.

Currently we only have a hypothesis that there are some worst
offenders vs lots of normal load. And we can't point fingers which
means that, say, sysfs, or other maintainers won't be too inclined to
fix anything.

If we would know for sure that lock class X is guilty. That would make
the situation much more actionable.

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v2] lockdep: Allow tuning tracing capacity constants.
  2020-09-16 12:14         ` Dmitry Vyukov
@ 2020-09-28  0:24           ` Tetsuo Handa
  2020-09-28  5:12             ` Dmitry Vyukov
  0 siblings, 1 reply; 17+ messages in thread
From: Tetsuo Handa @ 2020-09-28  0:24 UTC (permalink / raw)
  To: Dmitry Vyukov, Peter Zijlstra
  Cc: Ingo Molnar, Will Deacon, Andrew Morton, LKML, syzkaller

On 2020/09/16 21:14, Dmitry Vyukov wrote:
> On Wed, Sep 16, 2020 at 1:51 PM <peterz@infradead.org> wrote:
>>
>> On Wed, Sep 16, 2020 at 01:28:19PM +0200, Dmitry Vyukov wrote:
>>> On Fri, Sep 4, 2020 at 6:05 PM Tetsuo Handa
>>> <penguin-kernel@i-love.sakura.ne.jp> wrote:
>>>>
>>>> Hello. Can we apply this patch?
>>>>
>>>> This patch addresses top crashers for syzbot, and applying this patch
>>>> will help utilizing syzbot's resource for finding other bugs.
>>>
>>> Acked-by: Dmitry Vyukov <dvyukov@google.com>
>>>
>>> Peter, do you still have concerns with this?
>>
>> Yeah, I still hate it with a passion; it discourages thinking. A bad
>> annotation that blows up the lockdep storage, no worries, we'll just
>> increase this :/
>>
>> IIRC the issue with syzbot is that the current sysfs annotation is
>> pretty terrible and generates a gazillion classes, and syzbot likes
>> poking at /sys a lot and thus floods the system.
>>
>> I don't know enough about sysfs to suggest an alternative, and haven't
>> exactly had spare time to look into it either :/
>>
>> Examples of bad annotations is getting every CPU a separate class, that
>> leads to nr_cpus! chains if CPUs arbitrarily nest (nr_cpus^2 if there's
>> only a single nesting level).
> 
> Maybe on "BUG: MAX_LOCKDEP_CHAINS too low!" we should then aggregate,
> sort and show existing chains so that it's possible to identify if
> there are any worst offenders and who they are.
> 
> Currently we only have a hypothesis that there are some worst
> offenders vs lots of normal load. And we can't point fingers which
> means that, say, sysfs, or other maintainers won't be too inclined to
> fix anything.
> 
> If we would know for sure that lock class X is guilty. That would make
> the situation much more actionable.
> 

Dmitry is thinking that we need to use CONFIG_LOCKDEP=n temporary until lockdep
problems are resolved. ( https://github.com/google/syzkaller/issues/2140 )

But I think it is better to apply this patch (and revert this patch when it became
possible to identify if there are any worst offenders and who they are) than using
CONFIG_LOCKDEP=n.

CONFIG_LOCKDEP=n causes "#syz test" request to cause false response regarding locking
related issues, for we are not ready to enforce "retest without proposed patch
when test with proposed patch did not reproduce the crash".

I think that "not detecting lock related problems introduced by new patches" costs
more than "postpone fixing lock related problems in existing code".

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v2] lockdep: Allow tuning tracing capacity constants.
  2020-09-28  0:24           ` Tetsuo Handa
@ 2020-09-28  5:12             ` Dmitry Vyukov
  0 siblings, 0 replies; 17+ messages in thread
From: Dmitry Vyukov @ 2020-09-28  5:12 UTC (permalink / raw)
  To: Tetsuo Handa
  Cc: Peter Zijlstra, Ingo Molnar, Will Deacon, Andrew Morton, LKML, syzkaller

On Mon, Sep 28, 2020 at 2:24 AM Tetsuo Handa
<penguin-kernel@i-love.sakura.ne.jp> wrote:
>
> On 2020/09/16 21:14, Dmitry Vyukov wrote:
> > On Wed, Sep 16, 2020 at 1:51 PM <peterz@infradead.org> wrote:
> >>
> >> On Wed, Sep 16, 2020 at 01:28:19PM +0200, Dmitry Vyukov wrote:
> >>> On Fri, Sep 4, 2020 at 6:05 PM Tetsuo Handa
> >>> <penguin-kernel@i-love.sakura.ne.jp> wrote:
> >>>>
> >>>> Hello. Can we apply this patch?
> >>>>
> >>>> This patch addresses top crashers for syzbot, and applying this patch
> >>>> will help utilizing syzbot's resource for finding other bugs.
> >>>
> >>> Acked-by: Dmitry Vyukov <dvyukov@google.com>
> >>>
> >>> Peter, do you still have concerns with this?
> >>
> >> Yeah, I still hate it with a passion; it discourages thinking. A bad
> >> annotation that blows up the lockdep storage, no worries, we'll just
> >> increase this :/
> >>
> >> IIRC the issue with syzbot is that the current sysfs annotation is
> >> pretty terrible and generates a gazillion classes, and syzbot likes
> >> poking at /sys a lot and thus floods the system.
> >>
> >> I don't know enough about sysfs to suggest an alternative, and haven't
> >> exactly had spare time to look into it either :/
> >>
> >> Examples of bad annotations is getting every CPU a separate class, that
> >> leads to nr_cpus! chains if CPUs arbitrarily nest (nr_cpus^2 if there's
> >> only a single nesting level).
> >
> > Maybe on "BUG: MAX_LOCKDEP_CHAINS too low!" we should then aggregate,
> > sort and show existing chains so that it's possible to identify if
> > there are any worst offenders and who they are.
> >
> > Currently we only have a hypothesis that there are some worst
> > offenders vs lots of normal load. And we can't point fingers which
> > means that, say, sysfs, or other maintainers won't be too inclined to
> > fix anything.
> >
> > If we would know for sure that lock class X is guilty. That would make
> > the situation much more actionable.
> >
>
> Dmitry is thinking that we need to use CONFIG_LOCKDEP=n temporary until lockdep
> problems are resolved. ( https://github.com/google/syzkaller/issues/2140 )
>
> But I think it is better to apply this patch (and revert this patch when it became
> possible to identify if there are any worst offenders and who they are) than using
> CONFIG_LOCKDEP=n.
>
> CONFIG_LOCKDEP=n causes "#syz test" request to cause false response regarding locking
> related issues, for we are not ready to enforce "retest without proposed patch
> when test with proposed patch did not reproduce the crash".

FWIW patch testing for previously reported bugs should still work
because it uses the kernel config associated with the bug report.

> I think that "not detecting lock related problems introduced by new patches" costs
> more than "postpone fixing lock related problems in existing code".

^ permalink raw reply	[flat|nested] 17+ messages in thread

* [PATCH v3] lockdep: Allow tuning tracing capacity constants.
  2020-08-27 15:20 ` [PATCH v2] lockdep: Allow tuning tracing capacity constants Tetsuo Handa
  2020-09-04 16:05   ` Tetsuo Handa
@ 2020-10-10 12:58   ` Tetsuo Handa
  2020-10-18 13:02     ` Tetsuo Handa
  1 sibling, 1 reply; 17+ messages in thread
From: Tetsuo Handa @ 2020-10-10 12:58 UTC (permalink / raw)
  To: Peter Zijlstra, Ingo Molnar, Will Deacon
  Cc: Andrew Morton, linux-kernel, Dmitry Vyukov, Linus Torvalds

Since syzkaller continues various test cases until the kernel crashes,
syzkaller tends to examine more locking dependencies than normal systems.
As a result, syzbot is reporting that the fuzz testing was terminated
due to hitting upper limits lockdep can track [1] [2] [3].

Peter Zijlstra does not want to allow tuning these limits via kernel
config options, for such change discourages thinking. But currently we
are not actionable, for lockdep does not report the culprit for hitting
these limits [4].

Therefore, I propose this patch again, with a caveat that this patch is
expected to be reverted after lockdep becomes capable of reporting the
culprit, for I consider that "postpone fixing lock related problems in
existing code" is less painful than "not detecting lock related problems
introduced by new patches".

[1] https://syzkaller.appspot.com/bug?id=3d97ba93fb3566000c1c59691ea427370d33ea1b
[2] https://syzkaller.appspot.com/bug?id=381cb436fe60dc03d7fd2a092b46d7f09542a72a
[3] https://syzkaller.appspot.com/bug?id=a588183ac34c1437fc0785e8f220e88282e5a29f
[4] https://lkml.kernel.org/r/CACT4Y+agTiEF-1i9LbAgp-q_02oYF0kAPZGAAJ==-wx2Xh7xzQ@mail.gmail.com

Reported-by: syzbot <syzbot+cd0ec5211ac07c18c049@syzkaller.appspotmail.com>
Reported-by: syzbot <syzbot+91fd909b6e62ebe06131@syzkaller.appspotmail.com>
Reported-by: syzbot <syzbot+62ebe501c1ce9a91f68c@syzkaller.appspotmail.com>
Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
Acked-by: Dmitry Vyukov <dvyukov@google.com>
---
 kernel/locking/lockdep.c           |  2 +-
 kernel/locking/lockdep_internals.h |  8 +++---
 lib/Kconfig.debug                  | 40 ++++++++++++++++++++++++++++++
 3 files changed, 45 insertions(+), 5 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 2facbbd146ec..2144708a867c 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1349,7 +1349,7 @@ static int add_lock_to_list(struct lock_class *this,
 /*
  * For good efficiency of modular, we use power of 2
  */
-#define MAX_CIRCULAR_QUEUE_SIZE		4096UL
+#define MAX_CIRCULAR_QUEUE_SIZE		(1UL << CONFIG_LOCKDEP_CIRCULAR_QUEUE_BITS)
 #define CQ_MASK				(MAX_CIRCULAR_QUEUE_SIZE-1)
 
 /*
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index b0be1560ed17..cf7752847eb7 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -96,16 +96,16 @@ static const unsigned long LOCKF_USED_IN_IRQ_READ =
 #define MAX_STACK_TRACE_ENTRIES	262144UL
 #define STACK_TRACE_HASH_SIZE	8192
 #else
-#define MAX_LOCKDEP_ENTRIES	32768UL
+#define MAX_LOCKDEP_ENTRIES	(1UL << CONFIG_LOCKDEP_BITS)
 
-#define MAX_LOCKDEP_CHAINS_BITS	16
+#define MAX_LOCKDEP_CHAINS_BITS	CONFIG_LOCKDEP_CHAINS_BITS
 
 /*
  * Stack-trace: tightly packed array of stack backtrace
  * addresses. Protected by the hash_lock.
  */
-#define MAX_STACK_TRACE_ENTRIES	524288UL
-#define STACK_TRACE_HASH_SIZE	16384
+#define MAX_STACK_TRACE_ENTRIES	(1UL << CONFIG_LOCKDEP_STACK_TRACE_BITS)
+#define STACK_TRACE_HASH_SIZE	(1 << CONFIG_LOCKDEP_STACK_TRACE_HASH_BITS)
 #endif
 
 /*
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 0c781f912f9f..41d083be7ec3 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1311,6 +1311,46 @@ config LOCKDEP
 config LOCKDEP_SMALL
 	bool
 
+config LOCKDEP_BITS
+	int "Bitsize for MAX_LOCKDEP_ENTRIES"
+	depends on LOCKDEP && !LOCKDEP_SMALL
+	range 10 30
+	default 15
+	help
+	  Try increasing this value if you hit "BUG: MAX_LOCKDEP_ENTRIES too low!" message.
+
+config LOCKDEP_CHAINS_BITS
+	int "Bitsize for MAX_LOCKDEP_CHAINS"
+	depends on LOCKDEP && !LOCKDEP_SMALL
+	range 10 30
+	default 16
+	help
+	  Try increasing this value if you hit "BUG: MAX_LOCKDEP_CHAINS too low!" message.
+
+config LOCKDEP_STACK_TRACE_BITS
+	int "Bitsize for MAX_STACK_TRACE_ENTRIES"
+	depends on LOCKDEP && !LOCKDEP_SMALL
+	range 10 30
+	default 19
+	help
+	  Try increasing this value if you hit "BUG: MAX_STACK_TRACE_ENTRIES too low!" message.
+
+config LOCKDEP_STACK_TRACE_HASH_BITS
+	int "Bitsize for STACK_TRACE_HASH_SIZE"
+	depends on LOCKDEP && !LOCKDEP_SMALL
+	range 10 30
+	default 14
+	help
+	  Try increasing this value if you need large MAX_STACK_TRACE_ENTRIES.
+
+config LOCKDEP_CIRCULAR_QUEUE_BITS
+	int "Bitsize for elements in circular_queue struct"
+	depends on LOCKDEP
+	range 10 30
+	default 12
+	help
+	  Try increasing this value if you hit "lockdep bfs error:-1" warning due to __cq_enqueue() failure.
+
 config DEBUG_LOCKDEP
 	bool "Lock dependency engine debugging"
 	depends on DEBUG_KERNEL && LOCKDEP
-- 
2.18.4



^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v3] lockdep: Allow tuning tracing capacity constants.
  2020-10-10 12:58   ` [PATCH v3] " Tetsuo Handa
@ 2020-10-18 13:02     ` Tetsuo Handa
  0 siblings, 0 replies; 17+ messages in thread
From: Tetsuo Handa @ 2020-10-18 13:02 UTC (permalink / raw)
  To: Peter Zijlstra, Ingo Molnar, Will Deacon
  Cc: Andrew Morton, linux-kernel, Dmitry Vyukov, Linus Torvalds

Peter, what do you think? Can we apply this patch?

A potential for-now workaround for syzkaller would be to allow syzkaller
not to encounter the BUG: message (by masking BUG: message on the kernel
side) when hitting these limits, for continue testing until the kernel
crashes (due to other bugs like UAF) would be to some degree useful.

On 2020/10/10 21:58, Tetsuo Handa wrote:
> Since syzkaller continues various test cases until the kernel crashes,
> syzkaller tends to examine more locking dependencies than normal systems.
> As a result, syzbot is reporting that the fuzz testing was terminated
> due to hitting upper limits lockdep can track [1] [2] [3].
> 
> Peter Zijlstra does not want to allow tuning these limits via kernel
> config options, for such change discourages thinking. But currently we
> are not actionable, for lockdep does not report the culprit for hitting
> these limits [4].
> 
> Therefore, I propose this patch again, with a caveat that this patch is
> expected to be reverted after lockdep becomes capable of reporting the
> culprit, for I consider that "postpone fixing lock related problems in
> existing code" is less painful than "not detecting lock related problems
> introduced by new patches".
> 
> [1] https://syzkaller.appspot.com/bug?id=3d97ba93fb3566000c1c59691ea427370d33ea1b
> [2] https://syzkaller.appspot.com/bug?id=381cb436fe60dc03d7fd2a092b46d7f09542a72a
> [3] https://syzkaller.appspot.com/bug?id=a588183ac34c1437fc0785e8f220e88282e5a29f
> [4] https://lkml.kernel.org/r/CACT4Y+agTiEF-1i9LbAgp-q_02oYF0kAPZGAAJ==-wx2Xh7xzQ@mail.gmail.com
> 
> Reported-by: syzbot <syzbot+cd0ec5211ac07c18c049@syzkaller.appspotmail.com>
> Reported-by: syzbot <syzbot+91fd909b6e62ebe06131@syzkaller.appspotmail.com>
> Reported-by: syzbot <syzbot+62ebe501c1ce9a91f68c@syzkaller.appspotmail.com>
> Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
> Acked-by: Dmitry Vyukov <dvyukov@google.com>
> ---
>  kernel/locking/lockdep.c           |  2 +-
>  kernel/locking/lockdep_internals.h |  8 +++---
>  lib/Kconfig.debug                  | 40 ++++++++++++++++++++++++++++++
>  3 files changed, 45 insertions(+), 5 deletions(-)

^ permalink raw reply	[flat|nested] 17+ messages in thread

end of thread, back to index

Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-07-25  1:30 [PATCH] lockdep: Introduce CONFIG_LOCKDEP_LARGE Tetsuo Handa
2020-07-25  4:48 ` Dmitry Vyukov
2020-07-25  5:23   ` Tetsuo Handa
2020-08-04  2:36     ` Tetsuo Handa
2020-08-18  9:57       ` Dmitry Vyukov
2020-08-18 11:07         ` Tetsuo Handa
2020-08-18 12:02           ` Dmitry Vyukov
2020-08-18 12:59             ` Tetsuo Handa
2020-08-27 15:20 ` [PATCH v2] lockdep: Allow tuning tracing capacity constants Tetsuo Handa
2020-09-04 16:05   ` Tetsuo Handa
2020-09-16 11:28     ` Dmitry Vyukov
2020-09-16 11:50       ` peterz
2020-09-16 12:14         ` Dmitry Vyukov
2020-09-28  0:24           ` Tetsuo Handa
2020-09-28  5:12             ` Dmitry Vyukov
2020-10-10 12:58   ` [PATCH v3] " Tetsuo Handa
2020-10-18 13:02     ` Tetsuo Handa

LKML Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/lkml/0 lkml/git/0.git
	git clone --mirror https://lore.kernel.org/lkml/1 lkml/git/1.git
	git clone --mirror https://lore.kernel.org/lkml/2 lkml/git/2.git
	git clone --mirror https://lore.kernel.org/lkml/3 lkml/git/3.git
	git clone --mirror https://lore.kernel.org/lkml/4 lkml/git/4.git
	git clone --mirror https://lore.kernel.org/lkml/5 lkml/git/5.git
	git clone --mirror https://lore.kernel.org/lkml/6 lkml/git/6.git
	git clone --mirror https://lore.kernel.org/lkml/7 lkml/git/7.git
	git clone --mirror https://lore.kernel.org/lkml/8 lkml/git/8.git
	git clone --mirror https://lore.kernel.org/lkml/9 lkml/git/9.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 lkml lkml/ https://lore.kernel.org/lkml \
		linux-kernel@vger.kernel.org
	public-inbox-index lkml

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-kernel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git