kbuild: document recursive dependency limitation / resolution

Commit Message

Luis R. Rodriguez July 29, 2015, 8:09 p.m. UTC

From: "Luis R. Rodriguez" <[e-mail]>

Recursive dependency issues with kconfig are unavoidable due to
some limitations with kconfig, since these issues are recurring
provide a hint to the user how they can resolve these dependency
issues and also document why such limitation exists.

Cc: Geert Uytterhoeven <[e-mail]>
Cc: James Bottomley <[e-mail]>
Cc: Josh Triplett <[e-mail]>
Cc: Paul Bolle <[e-mail]>
Cc: Herbert Xu <[e-mail]>
Cc: Takashi Iwai <[e-mail]>
Cc: "Yann E. MORIN" <[e-mail]>
Cc: Michal Marek <[e-mail]>
Cc: Jonathan Corbet <[e-mail]>
Cc: [e-mail]
Cc: [e-mail]
Cc: [e-mail]
Signed-off-by: Luis R. Rodriguez <[e-mail]>
---

I've cc'd Roberto and Stefano as I think we might be able to in the
long term use some of their work on package dependency and solvers for
this problem [0] [1] [2]. This last part -- just consider it long term
focused.

[0] https://upsilon.cc/~zack/research/publications/splc2010-fd-deps.pdf
[1] https://ocaml.org/meetings/ocaml/2014/preferences-2014-09-05-slides.pdf
[2] https://www.youtube.com/watch?v=GSOcRQvZg8w

 Documentation/kbuild/kconfig-language.txt | 22 ++++++++++++++++++++++
 scripts/kconfig/symbol.c                  |  2 ++
 2 files changed, 24 insertions(+)

Comments

Randy Dunlap July 29, 2015, 8:34 p.m. UTC | #1

On 07/29/15 13:09, Luis R. Rodriguez wrote:
> From: "Luis R. Rodriguez" <[e-mail]>
> 
> Recursive dependency issues with kconfig are unavoidable due to
> some limitations with kconfig, since these issues are recurring
> provide a hint to the user how they can resolve these dependency
> issues and also document why such limitation exists.
> 
> Cc: Geert Uytterhoeven <[e-mail]>
> Cc: James Bottomley <[e-mail]>
> Cc: Josh Triplett <[e-mail]>
> Cc: Paul Bolle <[e-mail]>
> Cc: Herbert Xu <[e-mail]>
> Cc: Takashi Iwai <[e-mail]>
> Cc: "Yann E. MORIN" <[e-mail]>
> Cc: Michal Marek <[e-mail]>
> Cc: Jonathan Corbet <[e-mail]>
> Cc: [e-mail]
> Cc: [e-mail]
> Cc: [e-mail]
> Signed-off-by: Luis R. Rodriguez <[e-mail]>
> ---
> 
> I've cc'd Roberto and Stefano as I think we might be able to in the
> long term use some of their work on package dependency and solvers for
> this problem [0] [1] [2]. This last part -- just consider it long term
> focused.
> 
> [0] https://upsilon.cc/~zack/research/publications/splc2010-fd-deps.pdf
> [1] https://ocaml.org/meetings/ocaml/2014/preferences-2014-09-05-slides.pdf
> [2] https://www.youtube.com/watch?v=GSOcRQvZg8w
> 
>  Documentation/kbuild/kconfig-language.txt | 22 ++++++++++++++++++++++
>  scripts/kconfig/symbol.c                  |  2 ++
>  2 files changed, 24 insertions(+)
> 
> diff --git a/Documentation/kbuild/kconfig-language.txt b/Documentation/kbuild/kconfig-language.txt
> index 350f733bf2c7..7e0510d1cef7 100644
> --- a/Documentation/kbuild/kconfig-language.txt
> +++ b/Documentation/kbuild/kconfig-language.txt
> @@ -393,3 +393,25 @@ config FOO
>  	depends on BAR && m
>  
>  limits FOO to module (=m) or disabled (=n).
> +
> +Kconfig recursive dependency limitations
> +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> +
> +If you've hit the Kconfig error: "recursive dependency detected" you've run
> +into a recursive dependency issue with Kconfig. Kconfig does not do recursive
> +dependency resolution, this has a few implications for Kconfig file writers. In

maybe                 s/,/;/

> +practice it means that for instance if a driver A selects a few kconfig symbols
> +another driver B which selects any of these symbols cannot negate any of the
> +symbols the driver A selected.  Because of this current limitation developers
> +who run into this type of recursive dependency issue have two diverging
> +options:
> +
> +  a) Either swap all "select FOO" to "depends on FOO" or,
> +  b) Change the offending "depends on FOO" to "select FOO"
> +
> +Kconfig's limitations can be addressed by implementing a SAT solver for it,
> +but until then, Kconfig is limitted to require developers to use one of

                              limited

> +the above two mechanisms to address recursive dependency issues. For more
> +details you can refer to this thread and discussion:
> +
> +http://lkml.kernel.org/r/[e-mail]

Josh Triplett July 29, 2015, 8:54 p.m. UTC | #2

On Wed, Jul 29, 2015 at 01:09:16PM -0700, Luis R. Rodriguez wrote:
> From: "Luis R. Rodriguez" <[e-mail]>
> 
> Recursive dependency issues with kconfig are unavoidable due to
> some limitations with kconfig, since these issues are recurring
> provide a hint to the user how they can resolve these dependency
> issues and also document why such limitation exists.
> 
> Cc: Geert Uytterhoeven <[e-mail]>
> Cc: James Bottomley <[e-mail]>
> Cc: Josh Triplett <[e-mail]>
> Cc: Paul Bolle <[e-mail]>
> Cc: Herbert Xu <[e-mail]>
> Cc: Takashi Iwai <[e-mail]>
> Cc: "Yann E. MORIN" <[e-mail]>
> Cc: Michal Marek <[e-mail]>
> Cc: Jonathan Corbet <[e-mail]>
> Cc: [e-mail]
> Cc: [e-mail]
> Cc: [e-mail]
> Signed-off-by: Luis R. Rodriguez <[e-mail]>

As a minor nit, I would suggest saying that making Kbuild handle this
might require a full SAT solver, rather than the current phrasing that
suggests that a SAT solver is the right solution to this problem.  Let's
wait to make that conclusion until a kbuild patch shows up.

Otherwise, this seems quite sensible; thanks for documenting this bit of
tribal knowledge.

- Josh Triplett

> I've cc'd Roberto and Stefano as I think we might be able to in the
> long term use some of their work on package dependency and solvers for
> this problem [0] [1] [2]. This last part -- just consider it long term
> focused.
> 
> [0] https://upsilon.cc/~zack/research/publications/splc2010-fd-deps.pdf
> [1] https://ocaml.org/meetings/ocaml/2014/preferences-2014-09-05-slides.pdf
> [2] https://www.youtube.com/watch?v=GSOcRQvZg8w
> 
>  Documentation/kbuild/kconfig-language.txt | 22 ++++++++++++++++++++++
>  scripts/kconfig/symbol.c                  |  2 ++
>  2 files changed, 24 insertions(+)
> 
> diff --git a/Documentation/kbuild/kconfig-language.txt b/Documentation/kbuild/kconfig-language.txt
> index 350f733bf2c7..7e0510d1cef7 100644
> --- a/Documentation/kbuild/kconfig-language.txt
> +++ b/Documentation/kbuild/kconfig-language.txt
> @@ -393,3 +393,25 @@ config FOO
>  	depends on BAR && m
>  
>  limits FOO to module (=m) or disabled (=n).
> +
> +Kconfig recursive dependency limitations
> +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> +
> +If you've hit the Kconfig error: "recursive dependency detected" you've run
> +into a recursive dependency issue with Kconfig. Kconfig does not do recursive
> +dependency resolution, this has a few implications for Kconfig file writers. In
> +practice it means that for instance if a driver A selects a few kconfig symbols
> +another driver B which selects any of these symbols cannot negate any of the
> +symbols the driver A selected.  Because of this current limitation developers
> +who run into this type of recursive dependency issue have two diverging
> +options:
> +
> +  a) Either swap all "select FOO" to "depends on FOO" or,
> +  b) Change the offending "depends on FOO" to "select FOO"
> +
> +Kconfig's limitations can be addressed by implementing a SAT solver for it,
> +but until then, Kconfig is limitted to require developers to use one of
> +the above two mechanisms to address recursive dependency issues. For more
> +details you can refer to this thread and discussion:
> +
> +http://lkml.kernel.org/r/[e-mail]
> diff --git a/scripts/kconfig/symbol.c b/scripts/kconfig/symbol.c
> index 70c5ee189dce..4d61b7490dad 100644
> --- a/scripts/kconfig/symbol.c
> +++ b/scripts/kconfig/symbol.c
> @@ -1117,6 +1117,8 @@ static void sym_check_print_recursive(struct symbol *last_sym)
>  		if (stack->sym == last_sym)
>  			fprintf(stderr, "%s:%d:error: recursive dependency detected!\n",
>  				prop->file->name, prop->lineno);
> +			fprintf(stderr, "For a resolution refer to Documentation/kbuild/kconfig-language.txt\n");
> +			fprintf(stderr, "section \"Kconfig recursive dependency limitations\"\n");
>  		if (stack->expr) {
>  			fprintf(stderr, "%s:%d:\tsymbol %s %s value contains %s\n",
>  				prop->file->name, prop->lineno,
> -- 
> 2.3.2.209.gd67f9d5.dirty
> 
--
To unsubscribe from this list: send the line "unsubscribe linux-kbuild" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Michal Marek Aug. 4, 2015, 11:57 a.m. UTC | #3

Dne 29.7.2015 v 22:34 Randy Dunlap napsal(a):
> On 07/29/15 13:09, Luis R. Rodriguez wrote:
>> From: "Luis R. Rodriguez" <[e-mail]>
>>
>> Recursive dependency issues with kconfig are unavoidable due to
>> some limitations with kconfig, since these issues are recurring
>> provide a hint to the user how they can resolve these dependency
>> issues and also document why such limitation exists.

Good idea.


>> +Kconfig's limitations can be addressed by implementing a SAT solver for it,
>> +but until then, Kconfig is limitted to require developers to use one of
> 
>                               limited

should I apply the patch with the typo fixed or are you going to send a v2?

Thanks,
Michal
--
To unsubscribe from this list: send the line "unsubscribe linux-kbuild" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Paul Bolle Aug. 4, 2015, 12:05 p.m. UTC | #4

On di, 2015-08-04 at 13:57 +0200, Michal Marek wrote:
> should I apply the patch with the typo fixed or are you going to send 
> a v2?

I'm afraid I have been thinking about some comments for quite a few days
now. So a v2 would be appreciated.

Or, alternatively, Michal could perhaps wait another day and I promise
to actually make those comments. Is that OK?

Thanks either way,


Paul Bolle
--
To unsubscribe from this list: send the line "unsubscribe linux-kbuild" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Paul Bolle Aug. 5, 2015, 11:57 a.m. UTC | #5

[Once again I removed Yann from the addresses used. I suppose I'll just
send a trivial patch to remove Yann's M: line for MAINTAINERS.]

Hi Luis,

On wo, 2015-07-29 at 13:09 -0700, Luis R. Rodriguez wrote:
> Recursive dependency issues with kconfig are unavoidable due to
> some limitations with kconfig, since these issues are recurring
> provide a hint to the user how they can resolve these dependency
> issues and also document why such limitation exists.
> 
> Signed-off-by: Luis R. Rodriguez <[e-mail]>

Like Josh and Marek I find this a good idea. Because I like the idea
I'll be critical.

> --- a/Documentation/kbuild/kconfig-language.txt
> +++ b/Documentation/kbuild/kconfig-language.txt
> @@ -393,3 +393,25 @@ config FOO
>  	depends on BAR && m
>  
>  limits FOO to module (=m) or disabled (=n).
> +
> +Kconfig recursive dependency limitations
> +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> +
> +If you've hit the Kconfig error: "recursive dependency detected" you've run
> +into a recursive dependency issue with Kconfig. Kconfig does not do recursive
> +dependency resolution,

(True. But what could Kconfig do other than note that a chain of
select's and depend on's makes it run in circles? See below.)

>  this has a few implications for Kconfig file writers. In
> +practice it means that for instance if a driver A selects a few kconfig symbols
> +another driver B which selects any of these symbols cannot negate any of the
> +symbols the driver A selected.

I'm afraid I don't follow this.

> Because of this current limitation developers
> +who run into this type of recursive dependency issue have two diverging
> +options:
> +
> +  a) Either swap all "select FOO" to "depends on FOO" or,

all? "one or more" perhaps.

> +  b) Change the offending "depends on FOO" to "select FOO"

"the offending"? We're looking at a circle. So maybe:
    Change one or more "depends on BAR" to "select BAR"   

Which are both variations on a theme: stop running in circles. See below
for a (too?) small sample of 22 solutions I could easily find in git's
log. Swapping one or more select's with depend on's was done in two
thirds of these solutions.

> +Kconfig's limitations can be addressed by implementing a SAT solver for it,

Unlike Josh, I'm not familiar with SAT solvers, so it's hard to comment
on this.

But given the two building blocks involved:
    depends on
    select

it's clear you can make Kconfig run in circles. (Using only blocks of
one of those types could do that too. Kconfig uses both building blocks.
And in practice we always see blocks of both types involved when we make
Kconfig run in circles.)

What would a SAT solver do once it makes the obvious observation that
certain combinations of these two building blocks are circular?

> +but until then, Kconfig is limitted to require developers to use one of
> +the above two mechanisms to address recursive dependency issues. For more
> +details you can refer to this thread and discussion:
> +
> +http://lkml.kernel.org/r/[e-mail]

> --- a/scripts/kconfig/symbol.c
> +++ b/scripts/kconfig/symbol.c
> @@ -1117,6 +1117,8 @@ static void sym_check_print_recursive(struct

> +			fprintf(stderr, "For a resolution refer to Documentation/kbuild/kconfig-language.txt\n");
> +			fprintf(stderr, "section \"Kconfig recursive dependency limitations\"\n");

Nit: subsection.

Sorry for being so verbose. And thanks for doing this!


Paul Bolle


sample of solutions for recursive dependency errors
===================================================

21 commits contain the quote "recursive dependency detected". They
contain 22 fixes for 21 errors. (One error was solved twice. One commit
contained two fixes.)

All errors appear to involve one or more select's and one or more depend
on's.

commit		fix
======  	===
06b718c01208	select A -> depends on A
c22eacfe82f9	depends on A -> depends on B
6a91e854442c	select A -> depends on A
118c565a8f2e	select A -> select B
f004e5594705	select A -> depends on A
c7861f37b4c6	depends on A -> (null)
80c69915e5fb	select A -> (null)		(1)
c2218e26c0d0	select A -> depends on A	(1)
d6ae99d04e1c	select A -> depends on A
95ca19cf8cbf	select A -> depends on A
8f057d7bca54	depends on A -> (null)
8f057d7bca54	depends on A -> select A
a0701f04846e	select A -> depends on A
0c8b92f7f259	depends on A -> (null)
e4e9e0540928	select A -> depends on A	(2)
7453ea886e87	depends on A > (null)		(1)
7b1fff7e4fdf	select A -> depends on A
86c747d2a4f0	select A -> depends on A
d9f9ab51e55e	select A -> depends on A
0c51a4d8abd6	depends on A -> select A	(3)
e98062ed6dc4	select A -> depends on A	(3)
91e5d284a7f1	select A -> (null)     


(1) Partial (or no) quote of error.
(2) That seems to be the gist of that fix.
(3) Same error.
--
To unsubscribe from this list: send the line "unsubscribe linux-kbuild" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Luis Chamberlain Aug. 10, 2015, 6:57 p.m. UTC | #6

On Wed, Aug 05, 2015 at 01:57:20PM +0200, Paul Bolle wrote:
> > --- a/Documentation/kbuild/kconfig-language.txt
> > +++ b/Documentation/kbuild/kconfig-language.txt
> > @@ -393,3 +393,25 @@ config FOO
> >  	depends on BAR && m
> >  
> >  limits FOO to module (=m) or disabled (=n).
> > +
> > +Kconfig recursive dependency limitations
> > +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> > +
> > +If you've hit the Kconfig error: "recursive dependency detected" you've run
> > +into a recursive dependency issue with Kconfig. Kconfig does not do recursive
> > +dependency resolution,
> 
> (True. But what could Kconfig do other than note that a chain of
> select's and depend on's makes it run in circles? See below.)

That's the purpose of the documentation. To annotate as TODO to
hopefuly enthusiastic kconfig developers what would need to be
looked into, some small reference material, and obviously something
for the lazy driver developer who just wants to fix the problem within
what has been discussed and accepted.

> >  this has a few implications for Kconfig file writers. In
> > +practice it means that for instance if a driver A selects a few kconfig symbols
> > +another driver B which selects any of these symbols cannot negate any of the
> > +symbols the driver A selected.
> 
> I'm afraid I don't follow this.

You're right this could use a bit more lengthy description. Can you help?
How about:

If a driver A selects a series of features, and driver B selects its own set of
features, if both have a common selected feature, they then cannot negate each
other's features. This means that we have an ongoing lump sum of intersection
of features and this is always the largest collection of features.

I gave an example for you a while ago, below I provide it again to explain.
I will note you provided your own other example, I still like and prefer mine.
They're both similar, thought. We could perhaps combine? The shorter the
better.

Example extracted from: http://lkml.kernel.org/r/[e-mail]
-------------------------------------------------------------------------------
Let's say rock climbers hate locker rooms, but swimmer need them. We can
then have:

config GYM
        tristate
        default n

config LOCKER
        tristate
        default n
        depends on GYM

config SWIMMING
        tristate
        default n
        select GYM
        select LOCKER

config ROCK_CLIMBING
        tristate
        default n
        depends on !LOCKER
        select GYM

Kbuild seems to believe that because swimmers need lockers that rock climbers
need them too. That is obviously not true.

mcgrof@ergon ~/linux-next (git::your-swimming-dad)$ make allnoconfig
scripts/kconfig/conf --allnoconfig Kconfig
drivers/crypto/qat/Kconfig:25:error: recursive dependency detected!
drivers/crypto/qat/Kconfig:25:  symbol GYM is selected by ROCK_CLIMBING
drivers/crypto/qat/Kconfig:40:  symbol ROCK_CLIMBING depends on LOCKER
drivers/crypto/qat/Kconfig:29:  symbol LOCKER depends on GYM
#
# configuration written to .config
-------------------------------------------------------------------------------

> > +who run into this type of recursive dependency issue have two diverging
> > +options:
> > +
> > +  a) Either swap all "select FOO" to "depends on FOO" or,
> 
> all? "one or more" perhaps.

No I mean all, so in the above example the solution would be to switch
all select GYM to depends on GYM. One concrete example here was the
firmware issue with crypto stuff I was trying to add, ie firmware signing,
and a conflict with a driver I had. One option was to change all "select FW_LOADER"
to "depends on FW_LOADER" but since that was redundant given FW_LOADER is prevalent
my original proposed patch was to just remove all FW_LOADER selects [0]. Since
this was a lot of churn, I decided to go with option documented b) below.

[0] http://lkml.kernel.org/r/[e-mail]

> > +  b) Change the offending "depends on FOO" to "select FOO"
> 
> "the offending"? We're looking at a circle. So maybe:
>     Change one or more "depends on BAR" to "select BAR"   

The conflict would come up with *new* code so what I mean by
offending is to change the incoming code's use of "depends on"
to "select BAR".

> Which are both variations on a theme: stop running in circles. See below
> for a (too?) small sample of 22 solutions I could easily find in git's
> log. Swapping one or more select's with depend on's was done in two
> thirds of these solutions.

It may help to document this is the preferrred solution. This was the same
option I went with as well.

> > +Kconfig's limitations can be addressed by implementing a SAT solver for it,
> 
> Unlike Josh, I'm not familiar with SAT solvers, so it's hard to comment
> on this.
> 
> But given the two building blocks involved:
>     depends on
>     select
> 
> it's clear you can make Kconfig run in circles. (Using only blocks of
> one of those types could do that too. Kconfig uses both building blocks.
> And in practice we always see blocks of both types involved when we make
> Kconfig run in circles.)
> 
> What would a SAT solver do once it makes the obvious observation that
> certain combinations of these two building blocks are circular?

I think that's outside of the scope of the required documentation but
leave it to Josh or James to chime in if they wish.

> > +but until then, Kconfig is limitted to require developers to use one of
> > +the above two mechanisms to address recursive dependency issues. For more
> > +details you can refer to this thread and discussion:
> > +
> > +http://lkml.kernel.org/r/[e-mail]
> 
> > --- a/scripts/kconfig/symbol.c
> > +++ b/scripts/kconfig/symbol.c
> > @@ -1117,6 +1117,8 @@ static void sym_check_print_recursive(struct
> 
> > +			fprintf(stderr, "For a resolution refer to Documentation/kbuild/kconfig-language.txt\n");
> > +			fprintf(stderr, "section \"Kconfig recursive dependency limitations\"\n");
> 
> Nit: subsection.

Will change thanks.

> Sorry for being so verbose. And thanks for doing this!
> 
> 
> Paul Bolle
> 
> 
> sample of solutions for recursive dependency errors
> ===================================================
> 
> 21 commits contain the quote "recursive dependency detected". They
> contain 22 fixes for 21 errors. (One error was solved twice. One commit
> contained two fixes.)
> 
> All errors appear to involve one or more select's and one or more depend
> on's.
> 
> commit		fix
> ======  	===
> 06b718c01208	select A -> depends on A
> c22eacfe82f9	depends on A -> depends on B
> 6a91e854442c	select A -> depends on A
> 118c565a8f2e	select A -> select B
> f004e5594705	select A -> depends on A
> c7861f37b4c6	depends on A -> (null)
> 80c69915e5fb	select A -> (null)		(1)
> c2218e26c0d0	select A -> depends on A	(1)
> d6ae99d04e1c	select A -> depends on A
> 95ca19cf8cbf	select A -> depends on A
> 8f057d7bca54	depends on A -> (null)
> 8f057d7bca54	depends on A -> select A
> a0701f04846e	select A -> depends on A
> 0c8b92f7f259	depends on A -> (null)
> e4e9e0540928	select A -> depends on A	(2)
> 7453ea886e87	depends on A > (null)		(1)
> 7b1fff7e4fdf	select A -> depends on A
> 86c747d2a4f0	select A -> depends on A
> d9f9ab51e55e	select A -> depends on A
> 0c51a4d8abd6	depends on A -> select A	(3)
> e98062ed6dc4	select A -> depends on A	(3)
> 91e5d284a7f1	select A -> (null)     
> 
> 
> (1) Partial (or no) quote of error.
> (2) That seems to be the gist of that fix.
> (3) Same error.

Maybe I'll tack this on.

  Luis
--
To unsubscribe from this list: send the line "unsubscribe linux-kbuild" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Paul Bolle Sept. 3, 2015, 11:56 a.m. UTC | #7

Hi Luis,

(This landed in my Inbox when I was away from keyboard for a few weeks.
And then I dragged my feet a bit in answering this. Sorry about that.)

On ma, 2015-08-10 at 20:57 +0200, Luis R. Rodriguez wrote:
> On Wed, Aug 05, 2015 at 01:57:20PM +0200, Paul Bolle wrote:
> You're right this could use a bit more lengthy description. Can you help?

I'll try.

> How about:
> 
> If a driver A selects a series of features, and driver B selects its own set of
> features, if both have a common selected feature, they then cannot negate each
> other's features. This means that we have an ongoing lump sum of intersection
> of features and this is always the largest collection of features.
> 
> I gave an example for you a while ago, below I provide it again to explain.
> I will note you provided your own other example, I still like and prefer mine.
> They're both similar, thought. We could perhaps combine? The shorter the
> better.

I'll paste a condensed version of your example at the end of this
message. It triggers the same error. But perhaps it's too obvious to
serve as an example.

> Example extracted from: http://lkml.kernel.org/r/[e-mail]
> -------------------------------------------------------------------------------
> Let's say rock climbers hate locker rooms, but swimmer need them. We can
> then have:
> 
> config GYM
>         tristate
>         default n
> 
> config LOCKER
>         tristate
>         default n
>         depends on GYM
> 
> config SWIMMING
>         tristate
>         default n
>         select GYM
>         select LOCKER
> 
> config ROCK_CLIMBING
>         tristate
>         default n
>         depends on !LOCKER
>         select GYM
> 
> Kbuild seems to believe that because swimmers need lockers that rock climbers
> need them too. That is obviously not true.

(Could it be that the translation of
	config ROCK_CLIMBING
		depends on !LOCKER

into
	symbol ROCK_CLIMBING depends on LOCKER

is a bit confusing here?)

> mcgrof@ergon ~/linux-next (git::your-swimming-dad)$ make allnoconfig
> scripts/kconfig/conf --allnoconfig Kconfig
> drivers/crypto/qat/Kconfig:25:error: recursive dependency detected!
> drivers/crypto/qat/Kconfig:25:  symbol GYM is selected by ROCK_CLIMBING
> drivers/crypto/qat/Kconfig:40:  symbol ROCK_CLIMBING depends on LOCKER
> drivers/crypto/qat/Kconfig:29:  symbol LOCKER depends on GYM

I'll go through this example step by step (I haven't peeked at my
previous attempt and hope this new explanation is a bit clearer).

"The kconfig tools need to ensure that their input complies with the
configuration requirements specified in the various Kconfig files. In
order to do that they must determine the values that are possible for
all Kconfig symbols. And that is not possible if there is a circular
relation between two or more Kconfig symbols.

For example, what values are possible for GYM? ROCK_CLIMBING selects
GYM, which means that it influences the values that are possible for
GYM. (Eg, if ROCK_CLIMBING is 'y', GYM must be 'y' too.)

What influences ROCK_CLIMBING? ROCK_CLIMBING depends on !LOCKER. (So if
LOCKER is 'y' ROCK_CLIMBING can not be set.)

And what influences LOCKER? Well, LOCKER depends on GYM, so GYM
influences LOCKER.

But that is a problem. Because this means that in order to determine
what values are possible for GYM we need to look at GYM itself. In other
words, answering that question would make the kconfig tools run in a
circle. So the kconfig tools return the "recursive dependency detected"
error instead."

(Note that SWIMMING doesn't matter for this analysis.)

> #
> # configuration written to .config
> -------------------------------------------------------------------------------

> > Which are both variations on a theme: stop running in circles. See below
> > for a (too?) small sample of 22 solutions I could easily find in git's
> > log. Swapping one or more select's with depend on's was done in two
> > thirds of these solutions.
> 
> It may help to document this is the preferrred solution. This was the same
> option I went with as well.

Yes, I like your idea to offer one or more simple guidelines. I think we
just disagree on their wording. Perhaps it's just that I've looked into
all this kconfig stuff too often already to still be able to see how
other people might think about that dreaded recursive dependency error.

Thanks,


Paul Bolle

$ cat Kconfig.locker 
# test with 'make KBUILD_KCONFIG=Kconfig.locker menuconfig'
mainmenu "Luis' locker"

config GYM
	tristate

config LOCKER
	tristate
	depends on GYM

config ROCK_CLIMBING
	tristate
	depends on LOCKER
        select GYM
--
To unsubscribe from this list: send the line "unsubscribe linux-kbuild" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Luis Chamberlain Sept. 8, 2015, 1:12 p.m. UTC | #8

On Thu, Sep 3, 2015 at 4:56 AM, Paul Bolle <[e-mail]> wrote:
> Hi Luis,
>
> (This landed in my Inbox when I was away from keyboard for a few weeks.
> And then I dragged my feet a bit in answering this. Sorry about that.)

No worries.

> On ma, 2015-08-10 at 20:57 +0200, Luis R. Rodriguez wrote:
>> On Wed, Aug 05, 2015 at 01:57:20PM +0200, Paul Bolle wrote:
>> You're right this could use a bit more lengthy description. Can you help?
>
> I'll try.
>
>> How about:
>>
>> If a driver A selects a series of features, and driver B selects its own set of
>> features, if both have a common selected feature, they then cannot negate each
>> other's features. This means that we have an ongoing lump sum of intersection
>> of features and this is always the largest collection of features.
>>
>> I gave an example for you a while ago, below I provide it again to explain.
>> I will note you provided your own other example, I still like and prefer mine.
>> They're both similar, thought. We could perhaps combine? The shorter the
>> better.
>
> I'll paste a condensed version of your example at the end of this
> message. It triggers the same error. But perhaps it's too obvious to
> serve as an example.
>
>> Example extracted from: http://lkml.kernel.org/r/[e-mail]
>> -------------------------------------------------------------------------------
>> Let's say rock climbers hate locker rooms, but swimmer need them. We can
>> then have:
>>
>> config GYM
>>         tristate
>>         default n
>>
>> config LOCKER
>>         tristate
>>         default n
>>         depends on GYM
>>
>> config SWIMMING
>>         tristate
>>         default n
>>         select GYM
>>         select LOCKER
>>
>> config ROCK_CLIMBING
>>         tristate
>>         default n
>>         depends on !LOCKER
>>         select GYM
>>
>> Kbuild seems to believe that because swimmers need lockers that rock climbers
>> need them too. That is obviously not true.
>
> (Could it be that the translation of
>         config ROCK_CLIMBING
>                 depends on !LOCKER
>
> into
>         symbol ROCK_CLIMBING depends on LOCKER
>
> is a bit confusing here?)

For your example alternative? Well its just a different concise
example, that's all. I understand now our differences which I'll
explain below.

>> mcgrof@ergon ~/linux-next (git::your-swimming-dad)$ make allnoconfig
>> scripts/kconfig/conf --allnoconfig Kconfig
>> drivers/crypto/qat/Kconfig:25:error: recursive dependency detected!
>> drivers/crypto/qat/Kconfig:25:  symbol GYM is selected by ROCK_CLIMBING
>> drivers/crypto/qat/Kconfig:40:  symbol ROCK_CLIMBING depends on LOCKER
>> drivers/crypto/qat/Kconfig:29:  symbol LOCKER depends on GYM
>
> I'll go through this example step by step (I haven't peeked at my
> previous attempt and hope this new explanation is a bit clearer).
>
> "The kconfig tools need to ensure that their input complies with the
> configuration requirements specified in the various Kconfig files. In
> order to do that they must determine the values that are possible for
> all Kconfig symbols. And that is not possible if there is a circular
> relation between two or more Kconfig symbols.
>
> For example, what values are possible for GYM? ROCK_CLIMBING selects
> GYM, which means that it influences the values that are possible for
> GYM. (Eg, if ROCK_CLIMBING is 'y', GYM must be 'y' too.)
>
> What influences ROCK_CLIMBING? ROCK_CLIMBING depends on !LOCKER. (So if
> LOCKER is 'y' ROCK_CLIMBING can not be set.)
>
> And what influences LOCKER? Well, LOCKER depends on GYM, so GYM
> influences LOCKER.
>
> But that is a problem. Because this means that in order to determine
> what values are possible for GYM we need to look at GYM itself. In other
> words, answering that question would make the kconfig tools run in a
> circle. So the kconfig tools return the "recursive dependency detected"
> error instead."
>
> (Note that SWIMMING doesn't matter for this analysis.)

Ah but there lies our difference, you see you are trying to just
explain *why* and *what* a recursive issue is, I'm trying to explain a
very common type of issue that can creep up. I think we should
document both. Your example just tries to go word by word by word
tying to explain *why* and how we end up in a loop, I'm trying to show
a practical issue that is implicated by the recursive issue. My
example clearly shows a limitation as well that folks have to be aware
of.

>> #
>> # configuration written to .config
>> -------------------------------------------------------------------------------
>
>> > Which are both variations on a theme: stop running in circles. See below
>> > for a (too?) small sample of 22 solutions I could easily find in git's
>> > log. Swapping one or more select's with depend on's was done in two
>> > thirds of these solutions.
>>
>> It may help to document this is the preferrred solution. This was the same
>> option I went with as well.
>
> Yes, I like your idea to offer one or more simple guidelines. I think we
> just disagree on their wording. Perhaps it's just that I've looked into
> all this kconfig stuff too often already to still be able to see how
> other people might think about that dreaded recursive dependency error.

I'll respin, include both examples to first include your example and
walk people over the recursive issue, and then provide my example to
show the implications for features on drivers. I'll also now include
some references to SAT solver solution stuff for the eager beaver that
may want to try to solve these issues.

 Luis
--
To unsubscribe from this list: send the line "unsubscribe linux-kbuild" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Luis Chamberlain Sept. 23, 2015, 3:46 p.m. UTC | #9

On Wed, Jul 29, 2015 at 01:54:07PM -0700, [e-mail] wrote:
> On Wed, Jul 29, 2015 at 01:09:16PM -0700, Luis R. Rodriguez wrote:
> > From: "Luis R. Rodriguez" <[e-mail]>
> > 
> > Recursive dependency issues with kconfig are unavoidable due to
> > some limitations with kconfig, since these issues are recurring
> > provide a hint to the user how they can resolve these dependency
> > issues and also document why such limitation exists.
> > 
> > Cc: Geert Uytterhoeven <[e-mail]>
> > Cc: James Bottomley <[e-mail]>
> > Cc: Josh Triplett <[e-mail]>
> > Cc: Paul Bolle <[e-mail]>
> > Cc: Herbert Xu <[e-mail]>
> > Cc: Takashi Iwai <[e-mail]>
> > Cc: "Yann E. MORIN" <[e-mail]>
> > Cc: Michal Marek <[e-mail]>
> > Cc: Jonathan Corbet <[e-mail]>
> > Cc: [e-mail]
> > Cc: [e-mail]
> > Cc: [e-mail]
> > Signed-off-by: Luis R. Rodriguez <[e-mail]>
> 
> As a minor nit, I would suggest saying that making Kbuild handle this
> might require a full SAT solver, rather than the current phrasing that
> suggests that a SAT solver is the right solution to this problem.  Let's
> wait to make that conclusion until a kbuild patch shows up.

Thanks I've clarified this some more and expanding completely on the
section on SAT solver with some references for the eager beavers. I have
also found some other use cases for SAT solver on Linux but since that
is out of the scope of Kconfig I'll leave it outside of the patch but after
the commit log so even more eager beavers can take action.

> Otherwise, this seems quite sensible; thanks for documenting this bit of
> tribal knowledge.

Thanks, I'll respin finally.

  Luis
--
To unsubscribe from this list: send the line "unsubscribe linux-kbuild" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Luis Chamberlain Sept. 23, 2015, 3:48 p.m. UTC | #10

On Wed, Jul 29, 2015 at 01:34:50PM -0700, Randy Dunlap wrote:
> On 07/29/15 13:09, Luis R. Rodriguez wrote:
> > +
> > +Kconfig recursive dependency limitations
> > +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> > +
> > +If you've hit the Kconfig error: "recursive dependency detected" you've run
> > +into a recursive dependency issue with Kconfig. Kconfig does not do recursive
> > +dependency resolution, this has a few implications for Kconfig file writers. In
> 
> maybe                 s/,/;/

Fixed.

> > +practice it means that for instance if a driver A selects a few kconfig symbols
> > +another driver B which selects any of these symbols cannot negate any of the
> > +symbols the driver A selected.  Because of this current limitation developers
> > +who run into this type of recursive dependency issue have two diverging
> > +options:
> > +
> > +  a) Either swap all "select FOO" to "depends on FOO" or,
> > +  b) Change the offending "depends on FOO" to "select FOO"
> > +
> > +Kconfig's limitations can be addressed by implementing a SAT solver for it,
> > +but until then, Kconfig is limitted to require developers to use one of
> 
>                               limited
> 

I've re-written this section, thanks for the review.

  Luis
--
To unsubscribe from this list: send the line "unsubscribe linux-kbuild" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Luis Chamberlain Sept. 23, 2015, 3:50 p.m. UTC | #11

On Tue, Aug 04, 2015 at 01:57:21PM +0200, Michal Marek wrote:
> Dne 29.7.2015 v 22:34 Randy Dunlap napsal(a):
> > On 07/29/15 13:09, Luis R. Rodriguez wrote:
> >> From: "Luis R. Rodriguez" <[e-mail]>
> >>
> >> Recursive dependency issues with kconfig are unavoidable due to
> >> some limitations with kconfig, since these issues are recurring
> >> provide a hint to the user how they can resolve these dependency
> >> issues and also document why such limitation exists.
> 
> Good idea.

Great I've expanded a bit on the future required work to feed the curious
so that we don't idle lingering what to do next but rather get folks engaged
and so that they can know where to dive in.

> 
> >> +Kconfig's limitations can be addressed by implementing a SAT solver for it,
> >> +but until then, Kconfig is limitted to require developers to use one of
> > 
> >                               limited
> 
> should I apply the patch with the typo fixed or are you going to send a v2?

I'll respin a v3 now.

  Luis
--
To unsubscribe from this list: send the line "unsubscribe linux-kbuild" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Luis Chamberlain Sept. 23, 2015, 3:53 p.m. UTC | #12

On Thu, Sep 03, 2015 at 01:56:49PM +0200, Paul Bolle wrote:
> Hi Luis,
> 
> (This landed in my Inbox when I was away from keyboard for a few weeks.
> And then I dragged my feet a bit in answering this. Sorry about that.)

No worries I will note that I try to be as thorough so sadly this can go on
forever... I've taken your feedback and placed it first to explain *why* this
happens, then I added another subsection explaining one practical ramification
of such issue. Lastly I've exanded the patch with some homework for folks to
consider.

  Luis
--
To unsubscribe from this list: send the line "unsubscribe linux-kbuild" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch

diff --git a/Documentation/kbuild/kconfig-language.txt b/Documentation/kbuild/kconfig-language.txt
index 350f733bf2c7..7e0510d1cef7 100644
--- a/Documentation/kbuild/kconfig-language.txt
+++ b/Documentation/kbuild/kconfig-language.txt
@@ -393,3 +393,25 @@  config FOO
 	depends on BAR && m
 
 limits FOO to module (=m) or disabled (=n).
+
+Kconfig recursive dependency limitations
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+If you've hit the Kconfig error: "recursive dependency detected" you've run
+into a recursive dependency issue with Kconfig. Kconfig does not do recursive
+dependency resolution, this has a few implications for Kconfig file writers. In
+practice it means that for instance if a driver A selects a few kconfig symbols
+another driver B which selects any of these symbols cannot negate any of the
+symbols the driver A selected.  Because of this current limitation developers
+who run into this type of recursive dependency issue have two diverging
+options:
+
+  a) Either swap all "select FOO" to "depends on FOO" or,
+  b) Change the offending "depends on FOO" to "select FOO"
+
+Kconfig's limitations can be addressed by implementing a SAT solver for it,
+but until then, Kconfig is limitted to require developers to use one of
+the above two mechanisms to address recursive dependency issues. For more
+details you can refer to this thread and discussion:
+
+http://lkml.kernel.org/r/[e-mail]
diff --git a/scripts/kconfig/symbol.c b/scripts/kconfig/symbol.c
index 70c5ee189dce..4d61b7490dad 100644
--- a/scripts/kconfig/symbol.c
+++ b/scripts/kconfig/symbol.c
@@ -1117,6 +1117,8 @@  static void sym_check_print_recursive(struct symbol *last_sym)
 		if (stack->sym == last_sym)
 			fprintf(stderr, "%s:%d:error: recursive dependency detected!\n",
 				prop->file->name, prop->lineno);
+			fprintf(stderr, "For a resolution refer to Documentation/kbuild/kconfig-language.txt\n");
+			fprintf(stderr, "section \"Kconfig recursive dependency limitations\"\n");
 		if (stack->expr) {
 			fprintf(stderr, "%s:%d:\tsymbol %s %s value contains %s\n",
 				prop->file->name, prop->lineno,