kconfig - fix randconfig

kconfig - fix randconfig

[Sam Ravnborg]

kconfig failed to generate random values for choice values in
a choice block thus limiting the effect of builds based on randconfig
generated configs.

To test this I used this small config:

config MOD
	def_bool n
	option modules

choice CHOICE
        prompt "ABCD Choice"
        default A

config A
        tristate "A"

config B
        tristate "B"

config C
        tristate "C"

config D
        tristate "D"

endchoice

With the fix applied we now distribute the values more or
less even among the choice symbols.
And if MOD is enabled then we have several entries enabled.

Furhtermore calling randconfig several times in row made it
generate the same config as it used a second based seed.

Two patches follows - they are also at kfixes.git

	Sam

[PATCH 1/2] kconfig: fix randconfig for choice blocks

[Sam Ravnborg]

Ingo Molnar reported that 'make randconfig' was not covering
choice blocks properly, resulting in certain config options
being left out of randconfig testing altogether.

With the following patch we:
- properly randomize choice value for normal choice blocks
- properly randomize for multi choice blocks
- added several comments to explain what is going on

The root cause of the bug was that SYMBOL_VALID was set on the
symbol representing the choice block so clearing this did
the trick initially.
But testign revealed a few more issues that is now fixed.

Reported-by: Ingo Molnar <mingo@elte.hu>
Cc: Ingo Molnar <mingo@elte.hu>
Cc: Roman Zippel <zippel@linux-m68k.org>
Signed-off-by: Sam Ravnborg <sam@ravnborg.org>
---
 scripts/kconfig/confdata.c |   51 +++++++++++++++++++++++++++++++-------------
 1 files changed, 36 insertions(+), 15 deletions(-)

diff --git a/scripts/kconfig/confdata.c b/scripts/kconfig/confdata.c
index 830d9ea..273d738 100644
--- a/scripts/kconfig/confdata.c
+++ b/scripts/kconfig/confdata.c
@@ -843,7 +843,7 @@ void conf_set_all_new_symbols(enum conf_def_mode mode)
 			default:
 				continue;
 			}
-			if (!sym_is_choice(sym) || mode != def_random)
+			if (!(sym_is_choice(sym) && mode == def_random))
 				sym->flags |= SYMBOL_DEF_USER;
 			break;
 		default:
@@ -856,28 +856,49 @@ void conf_set_all_new_symbols(enum conf_def_mode mode)
 
 	if (mode != def_random)
 		return;
-
+	/*
+	 * We have different type of choice blocks.
+	 * If curr.tri equal to mod then we can select several
+	 * choice symbols in one block.
+	 * In this case we do nothing.
+	 * If curr.tri equal yes then only one symbol can be
+	 * selected in a choice block and we set it to yes,
+	 * and the rest to no.
+	 */
 	for_all_symbols(i, csym) {
 		if (sym_has_value(csym) || !sym_is_choice(csym))
 			continue;
 
 		sym_calc_value(csym);
+
+		if (csym->curr.tri != yes)
+			continue;
+
 		prop = sym_get_choice_prop(csym);
-		def = -1;
-		while (1) {
-			cnt = 0;
-			expr_list_for_each_sym(prop->expr, e, sym) {
-				if (sym->visible == no)
-					continue;
-				if (def == cnt++) {
-					csym->def[S_DEF_USER].val = sym;
-					break;
-				}
+
+		/* count entries in choice block */
+		cnt = 0;
+		expr_list_for_each_sym(prop->expr, e, sym)
+			cnt++;
+
+		/*
+		 * find a random value and set it to yes,
+		 * set the rest to no so we have only one set
+		 */
+		def = (rand() % cnt);
+
+		cnt = 0;
+		expr_list_for_each_sym(prop->expr, e, sym) {
+			if (def == cnt++) {
+				sym->def[S_DEF_USER].tri = yes;
+				csym->def[S_DEF_USER].val = sym;
+			}
+			else {
+				sym->def[S_DEF_USER].tri = no;
 			}
-			if (def >= 0 || cnt < 2)
-				break;
-			def = (rand() % cnt) + 1;
 		}
 		csym->flags |= SYMBOL_DEF_USER;
+		/* clear VALID to get value calculated */
+		csym->flags &= ~(SYMBOL_VALID);
 	}
 }
-- 
1.6.0.2.GIT

[PATCH 2/2] kconfig: improve seed in randconfig

[Sam Ravnborg]

'make randconfig' uses glibc's rand function, and the seed of
that PRNG is set via:

			srand(time(NULL));

But 'time()' only increases once every second - freezing the
randconfig result within a single second.

My Nehalem testbox does randconfig much faster than 1 second
 and i have a few scripts that do 'randconfig until condition X'
loops.

Those scripts currently waste a lot of CPU time due to randconfig
changing its seed only once per second currently.

Change the seed to be micrseconds based. (I checked the statistical
spread of the seed - the now.tv_sec*now.tv_usec multiplication
there further improves it.)

Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Sam Ravnborg <sam@ravnborg.org>
---
 scripts/kconfig/conf.c |   15 ++++++++++++++-
 1 files changed, 14 insertions(+), 1 deletions(-)

diff --git a/scripts/kconfig/conf.c b/scripts/kconfig/conf.c
index 3e1057f..4f1b488 100644
--- a/scripts/kconfig/conf.c
+++ b/scripts/kconfig/conf.c
@@ -11,6 +11,7 @@
 #include <time.h>
 #include <unistd.h>
 #include <sys/stat.h>
+#include <sys/time.h>
 
 #define LKC_DIRECT_LINK
 #include "lkc.h"
@@ -464,9 +465,21 @@ int main(int ac, char **av)
 			input_mode = set_yes;
 			break;
 		case 'r':
+		{
+			struct timeval now;
+			unsigned int seed;
+
+			/*
+			 * Use microseconds derived seed:
+			 */
+			gettimeofday(&now, NULL);
+
+			seed = (unsigned int)(now.tv_sec*now.tv_usec);
+			srand(seed);
+
 			input_mode = set_random;
-			srand(time(NULL));
 			break;
+		}
 		case 'h':
 			printf(_("See README for usage info\n"));
 			exit(0);
-- 
1.6.0.2.GIT

Re: [PATCH 2/2] kconfig: improve seed in randconfig

[Geert Uytterhoeven]

On Sun, Mar 15, 2009 at 11:28, Sam Ravnborg <sam@ravnborg.org> wrote:
> 'make randconfig' uses glibc's rand function, and the seed of
> that PRNG is set via:
>
>                        srand(time(NULL));
>
> But 'time()' only increases once every second - freezing the
> randconfig result within a single second.
>
> My Nehalem testbox does randconfig much faster than 1 second
>  and i have a few scripts that do 'randconfig until condition X'
> loops.
>
> Those scripts currently waste a lot of CPU time due to randconfig
> changing its seed only once per second currently.
>
> Change the seed to be micrseconds based. (I checked the statistical
> spread of the seed - the now.tv_sec*now.tv_usec multiplication
> there further improves it.)

> +                       gettimeofday(&now, NULL);
> +
> +                       seed = (unsigned int)(now.tv_sec*now.tv_usec);

Just wondering: may there be some platforms that don't offer microsecond
resolution, and tv_usec is always zero?

Gr{oetje,eeting}s,

						Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
							    -- Linus Torvalds

Re: [PATCH 2/2] kconfig: improve seed in randconfig

[Sam Ravnborg]

On Sun, Mar 15, 2009 at 11:53:03AM +0100, Geert Uytterhoeven wrote:
> On Sun, Mar 15, 2009 at 11:28, Sam Ravnborg <sam@ravnborg.org> wrote:
> > 'make randconfig' uses glibc's rand function, and the seed of
> > that PRNG is set via:
> >
> >                        srand(time(NULL));
> >
> > But 'time()' only increases once every second - freezing the
> > randconfig result within a single second.
> >
> > My Nehalem testbox does randconfig much faster than 1 second
> >  and i have a few scripts that do 'randconfig until condition X'
> > loops.
> >
> > Those scripts currently waste a lot of CPU time due to randconfig
> > changing its seed only once per second currently.
> >
> > Change the seed to be micrseconds based. (I checked the statistical
> > spread of the seed - the now.tv_sec*now.tv_usec multiplication
> > there further improves it.)
> 
> > +                       gettimeofday(&now, NULL);
> > +
> > +                       seed = (unsigned int)(now.tv_sec*now.tv_usec);
> 
> Just wondering: may there be some platforms that don't offer microsecond
> resolution, and tv_usec is always zero?
That would indeed be bad for the seed.
Googling did not turn up anything.

	Sam

Re: [PATCH 2/2] kconfig: improve seed in randconfig

[Ingo Molnar]

* Sam Ravnborg <sam@ravnborg.org> wrote:

> On Sun, Mar 15, 2009 at 11:53:03AM +0100, Geert Uytterhoeven wrote:
> > On Sun, Mar 15, 2009 at 11:28, Sam Ravnborg <sam@ravnborg.org> wrote:
> > > 'make randconfig' uses glibc's rand function, and the seed of
> > > that PRNG is set via:
> > >
> > >                        srand(time(NULL));
> > >
> > > But 'time()' only increases once every second - freezing the
> > > randconfig result within a single second.
> > >
> > > My Nehalem testbox does randconfig much faster than 1 second
> > >  and i have a few scripts that do 'randconfig until condition X'
> > > loops.
> > >
> > > Those scripts currently waste a lot of CPU time due to randconfig
> > > changing its seed only once per second currently.
> > >
> > > Change the seed to be micrseconds based. (I checked the statistical
> > > spread of the seed - the now.tv_sec*now.tv_usec multiplication
> > > there further improves it.)
> > 
> > > +                       gettimeofday(&now, NULL);
> > > +
> > > +                       seed = (unsigned int)(now.tv_sec*now.tv_usec);
> > 
> > Just wondering: may there be some platforms that don't offer microsecond
> > resolution, and tv_usec is always zero?
> That would indeed be bad for the seed.
> Googling did not turn up anything.

doing:

         seed = (unsigned int)((now.tv_sec+1)*(now.tv_usec+1));

ought to settle any practical doubts.

	Ing

Re: [PATCH 2/2] kconfig: improve seed in randconfig

[Alexander van Heukelum]

On Sun, 15 Mar 2009 19:54:07 +0100, "Ingo Molnar" <mingo@elte.hu> said:
> 
> * Sam Ravnborg <sam@ravnborg.org> wrote:
> 
> > On Sun, Mar 15, 2009 at 11:53:03AM +0100, Geert Uytterhoeven wrote:
> > > On Sun, Mar 15, 2009 at 11:28, Sam Ravnborg <sam@ravnborg.org> wrote:
> > > > 'make randconfig' uses glibc's rand function, and the seed of
> > > > that PRNG is set via:
> > > >
> > > >                        srand(time(NULL));
> > > >
> > > > But 'time()' only increases once every second - freezing the
> > > > randconfig result within a single second.
> > > >
> > > > My Nehalem testbox does randconfig much faster than 1 second
> > > >  and i have a few scripts that do 'randconfig until condition X'
> > > > loops.
> > > >
> > > > Those scripts currently waste a lot of CPU time due to randconfig
> > > > changing its seed only once per second currently.
> > > >
> > > > Change the seed to be micrseconds based. (I checked the statistical
> > > > spread of the seed - the now.tv_sec*now.tv_usec multiplication
> > > > there further improves it.)
> > > 
> > > > +                       gettimeofday(&now, NULL);
> > > > +
> > > > +                       seed = (unsigned int)(now.tv_sec*now.tv_usec);
> > > 
> > > Just wondering: may there be some platforms that don't offer microsecond
> > > resolution, and tv_usec is always zero?
> > That would indeed be bad for the seed.
> > Googling did not turn up anything.
> 
> doing:
> 
>          seed = (unsigned int)((now.tv_sec+1)*(now.tv_usec+1));
> 
> ought to settle any practical doubts.

Or maybe (and I think better...)

    seed = (unsigned int)(now.tv_sec ^ now.tv_usec);

Greetings,
    Alexander

> 	Ing

o :)

> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel"
> in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 
> 

Re: [PATCH 2/2] kconfig: improve seed in randconfig

[Sam Ravnborg]

> > 
> >          seed = (unsigned int)((now.tv_sec+1)*(now.tv_usec+1));
> > 
> > ought to settle any practical doubts.
> 
> Or maybe (and I think better...)
> 
>     seed = (unsigned int)(now.tv_sec ^ now.tv_usec);

Maybe better - but the one suggested by Ingo is more intuitive,
and is what I implmented already.

I have pushed out the following patch.

[And I know it breaks the 80 char limit].

	Sam

commit b0fe551000179c868d46266278a890eab878baca
Author: Ingo Molnar <mingo@elte.hu>
Date:   Thu Mar 12 15:15:31 2009 +0100

    kconfig: improve seed in randconfig
    
    'make randconfig' uses glibc's rand function, and the seed of
    that PRNG is set via:
    
    			srand(time(NULL));
    
    But 'time()' only increases once every second - freezing the
    randconfig result within a single second.
    
    My Nehalem testbox does randconfig much faster than 1 second
     and i have a few scripts that do 'randconfig until condition X'
    loops.
    
    Those scripts currently waste a lot of CPU time due to randconfig
    changing its seed only once per second currently.
    
    Change the seed to be micrseconds based. (I checked the statistical
    spread of the seed - the now.tv_sec*now.tv_usec multiplication
    there further improves it.)
    
    Signed-off-by: Ingo Molnar <mingo@elte.hu>
    Cc: Roman Zippel <zippel@linux-m68k.org>
    [sam: fix for systems where usec is zero - noticed by Geert Uytterhoeven]
    Signed-off-by: Sam Ravnborg <sam@ravnborg.org>

diff --git a/scripts/kconfig/conf.c b/scripts/kconfig/conf.c
index 3e1057f..d190092 100644
--- a/scripts/kconfig/conf.c
+++ b/scripts/kconfig/conf.c
@@ -11,6 +11,7 @@
 #include <time.h>
 #include <unistd.h>
 #include <sys/stat.h>
+#include <sys/time.h>
 
 #define LKC_DIRECT_LINK
 #include "lkc.h"
@@ -464,9 +465,22 @@ int main(int ac, char **av)
 			input_mode = set_yes;
 			break;
 		case 'r':
+		{
+			struct timeval now;
+			unsigned int seed;
+
+			/*
+			 * Use microseconds derived seed,
+			 * compensate for systems where it may be zero
+			 */
+			gettimeofday(&now, NULL);
+
+			seed = (unsigned int)((now.tv_sec + 1) * (now.tv_usec + 1));
+			srand(seed);
+
 			input_mode = set_random;
-			srand(time(NULL));
 			break;
+		}
 		case 'h':
 			printf(_("See README for usage info\n"));
 			exit(0);