[PATCH REPOST for 2.6.25] Use an own random generator for pageattr-test.c

[PATCH REPOST for 2.6.25] Use an own random generator for pageattr-test.c

[Andi Kleen]

Use an own random generator for pageattr-test.c

[Repost. Please ack/nack. This is a bug fix and imho a .25 late merge 
candidate because it fixes a subtle bug]

pageattr-test attempts to be repeatable and uses srandom32 to get a 
repeatable random number sequence.

Using srandom32() wasn't a good idea for various reasons:
- it is per cpu and if the cpu changes on a preemptible kernel it gets lost
- networking and random32 puts in some own state
- srandom32() does not actually reset the state, but just adds bits to 
it

Instead use a very simple private standard rnd that gives repeatable
results. I took the reference rand() from ISO-C.

Signed-off-by: Andi Kleen <ak@suse.de>

---
 arch/x86/mm/pageattr-test.c |   11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

Index: linux/arch/x86/mm/pageattr-test.c
===================================================================
--- linux.orig/arch/x86/mm/pageattr-test.c
+++ linux/arch/x86/mm/pageattr-test.c
@@ -101,6 +101,14 @@ static int print_split(struct split_stat
 static unsigned long addr[NTEST];
 static unsigned int len[NTEST];
 
+static int next = 100;
+
+static unsigned my_rand(void)
+{
+	next = next * 1103515245 + 12345;
+	return next;
+}
+
 /* Change the global bit on random pages in the direct mapping */
 static int pageattr_test(void)
 {
@@ -123,10 +131,9 @@ static int pageattr_test(void)
 	memset(bm, 0, (max_pfn_mapped + 7) / 8);
 
 	failed += print_split(&sa);
-	srandom32(100);
 
 	for (i = 0; i < NTEST; i++) {
-		unsigned long pfn = random32() % max_pfn_mapped;
+		unsigned long pfn = my_rand() % max_pfn_mapped;
 
 		addr[i] = (unsigned long)__va(pfn << PAGE_SHIFT);
 		len[i] = random32() % 100;

Re: [PATCH REPOST for 2.6.25] Use an own random generator for pageattr-test.c

[Andrew Morton]

On Tue, 11 Mar 2008 02:30:14 +0100 Andi Kleen <andi@firstfloor.org> wrote:

> Use an own random generator for pageattr-test.c
> 
> [Repost. Please ack/nack. This is a bug fix and imho a .25 late merge 
> candidate because it fixes a subtle bug]

An Ingo/Thomas thing.

> pageattr-test attempts to be repeatable and uses srandom32 to get a 
> repeatable random number sequence.
> 
> Using srandom32() wasn't a good idea for various reasons:
> - it is per cpu and if the cpu changes on a preemptible kernel it gets lost
> - networking and random32 puts in some own state
> - srandom32() does not actually reset the state, but just adds bits to 
> it
> 
> Instead use a very simple private standard rnd that gives repeatable
> results. I took the reference rand() from ISO-C.
> 
> Signed-off-by: Andi Kleen <ak@suse.de>
> 
> ---
>  arch/x86/mm/pageattr-test.c |   11 +++++++++--
>  1 file changed, 9 insertions(+), 2 deletions(-)
> 
> Index: linux/arch/x86/mm/pageattr-test.c
> ===================================================================
> --- linux.orig/arch/x86/mm/pageattr-test.c
> +++ linux/arch/x86/mm/pageattr-test.c
> @@ -101,6 +101,14 @@ static int print_split(struct split_stat
>  static unsigned long addr[NTEST];
>  static unsigned int len[NTEST];
>  
> +static int next = 100;
> +
> +static unsigned my_rand(void)
> +{
> +	next = next * 1103515245 + 12345;
> +	return next;
> +}

`next' should be local to my_rand().

>  /* Change the global bit on random pages in the direct mapping */
>  static int pageattr_test(void)
>  {
> @@ -123,10 +131,9 @@ static int pageattr_test(void)
>  	memset(bm, 0, (max_pfn_mapped + 7) / 8);
>  
>  	failed += print_split(&sa);
> -	srandom32(100);
>  
>  	for (i = 0; i < NTEST; i++) {
> -		unsigned long pfn = random32() % max_pfn_mapped;
> +		unsigned long pfn = my_rand() % max_pfn_mapped;
>  
>  		addr[i] = (unsigned long)__va(pfn << PAGE_SHIFT);
>  		len[i] = random32() % 100;

Re: [PATCH REPOST for 2.6.25] Use an own random generator for pageattr-test.c

[Thomas Gleixner]

On Tue, 11 Mar 2008, Andi Kleen wrote:
> Use an own random generator for pageattr-test.c
> 
> [Repost. Please ack/nack. This is a bug fix and imho a .25 late merge 
> candidate because it fixes a subtle bug]

Care to point out which "subtle bug" is fixed ? 

You replace a random generator by another to get repeateable
sequences. The non repeatability of the cpa test patterns is hardly a
"subtle bug".

Thanks,

	tglx

Re: [PATCH REPOST for 2.6.25] Use an own random generator for pageattr-test.c

[Andi Kleen]

On Tue, Mar 11, 2008 at 09:25:21AM +0100, Thomas Gleixner wrote:
> On Tue, 11 Mar 2008, Andi Kleen wrote:
> > Use an own random generator for pageattr-test.c
> > 
> > [Repost. Please ack/nack. This is a bug fix and imho a .25 late merge 
> > candidate because it fixes a subtle bug]
> 
> Care to point out which "subtle bug" is fixed ? 
> 
> You replace a random generator by another to get repeateable
> sequences. The non repeatability of the cpa test patterns is hardly a
> "subtle bug".

The subtle bug(s) are first that it is not repeatable (it really should),
then that it only initializes the CPU where the code first runs
(since srandom32 is per CPU) and later might change CPUs and then that it 
adds totally unnecessary state bits to CPU #0 (or whatever runs first).

-Andii

Re: [PATCH REPOST for 2.6.25] Use an own random generator for pageattr-test.c

[Thomas Gleixner]

On Tue, 11 Mar 2008, Andi Kleen wrote:

> On Tue, Mar 11, 2008 at 09:25:21AM +0100, Thomas Gleixner wrote:
> > On Tue, 11 Mar 2008, Andi Kleen wrote:
> > > Use an own random generator for pageattr-test.c
> > > 
> > > [Repost. Please ack/nack. This is a bug fix and imho a .25 late merge 
> > > candidate because it fixes a subtle bug]
> > 
> > Care to point out which "subtle bug" is fixed ? 
> > 
> > You replace a random generator by another to get repeateable
> > sequences. The non repeatability of the cpa test patterns is hardly a
> > "subtle bug".
> 
> The subtle bug(s) are first that it is not repeatable (it really should),

As I said before. It's hardly a bug. In fact it is questionable
whether fully reproducible test patterns are desired.

> then that it only initializes the CPU where the code first runs
> (since srandom32 is per CPU) and later might change CPUs and then that it 
> adds totally unnecessary state bits to CPU #0 (or whatever runs first).

Can you please elaborate why changing the seed of the random generator
is a bug ? Networking reseeds the random generator itself, so what ?

Thanks,
	tglx

Re: [PATCH REPOST for 2.6.25] Use an own random generator for pageattr-test.c

[Andi Kleen]

On Tue, Mar 11, 2008 at 12:41:13PM +0100, Thomas Gleixner wrote:
> 
> 
> On Tue, 11 Mar 2008, Andi Kleen wrote:
> 
> > On Tue, Mar 11, 2008 at 09:25:21AM +0100, Thomas Gleixner wrote:
> > > On Tue, 11 Mar 2008, Andi Kleen wrote:
> > > > Use an own random generator for pageattr-test.c
> > > > 
> > > > [Repost. Please ack/nack. This is a bug fix and imho a .25 late merge 
> > > > candidate because it fixes a subtle bug]
> > > 
> > > Care to point out which "subtle bug" is fixed ? 
> > > 
> > > You replace a random generator by another to get repeateable
> > > sequences. The non repeatability of the cpa test patterns is hardly a
> > > "subtle bug".
> > 
> > The subtle bug(s) are first that it is not repeatable (it really should),
> 
> As I said before. It's hardly a bug. In fact it is questionable
> whether fully reproducible test patterns are desired.

Ok then you won't be able to repeat the test ever.

I consider this bad practice in test code because it makes it impossible
to stabilize bugs and when I wrote it I tried to avoid by using the 
srandom32(). But I originally fell into the trap of assuming it had the 
same semantics of stdlib srandom() which it didn't. This patch was
my attempt to fix that mistake.

> 
> > then that it only initializes the CPU where the code first runs
> > (since srandom32 is per CPU) and later might change CPUs and then that it 
> > adds totally unnecessary state bits to CPU #0 (or whatever runs first).
> 
> Can you please elaborate why changing the seed of the random generator
> is a bug ? Networking reseeds the random generator itself, so what ?

It adds a non random seed which does not add any randomness only to CPU #0.
Strictly it doesn't hurt very much, but it's also not useful for anything.

-Andi

Re: [PATCH REPOST for 2.6.25] Use an own random generator for pageattr-test.c

[Thomas Gleixner]

On Tue, 11 Mar 2008, Andi Kleen wrote:
> > > > > Use an own random generator for pageattr-test.c
> > > > > 
> > > > > [Repost. Please ack/nack. This is a bug fix and imho a .25 late merge 
> > > > > candidate because it fixes a subtle bug]
> > > > 
> > > > Care to point out which "subtle bug" is fixed ? 
> > > > 
> > > > You replace a random generator by another to get repeateable
> > > > sequences. The non repeatability of the cpa test patterns is hardly a
> > > > "subtle bug".
> > > 
> > > The subtle bug(s) are first that it is not repeatable (it really should),
> > 
> > As I said before. It's hardly a bug. In fact it is questionable
> > whether fully reproducible test patterns are desired.
> 
> Ok then you won't be able to repeat the test ever.
> 
> I consider this bad practice in test code because it makes it impossible
> to stabilize bugs

Test code with constant test patterns tend to miss the corner case
bugs, while random pattern test cases hit them assumed that there is a
broad enough tester base. 

It's a question of how you write such test code to achieve
reproducability. It's not rocket science to track the variables of a
test run and print them along with the printk, when a wrong state is
detected. That way you can inject them for reproduction.

> and when I wrote it I tried to avoid by using the 
> srandom32(). But I originally fell into the trap of assuming it had the 
> same semantics of stdlib srandom() which it didn't. This patch was
> my attempt to fix that mistake.

Well, I agree that you did not intend to code it that way, but calling
it a subtle bug, which needs to be fixed for .25, is just misleading.

> > > then that it only initializes the CPU where the code first runs
> > > (since srandom32 is per CPU) and later might change CPUs and then that it 
> > > adds totally unnecessary state bits to CPU #0 (or whatever runs first).
> > 
> > Can you please elaborate why changing the seed of the random generator
> > is a bug ? Networking reseeds the random generator itself, so what ?
> 
> It adds a non random seed which does not add any randomness only to CPU #0.
> Strictly it doesn't hurt very much, but it's also not useful for anything.

Exactly. Again it's not a subtle bug. It's useless code which does no
harm at all. We can safely dispose that in .26.

Thanks,

	tglx

Re: [PATCH REPOST for 2.6.25] Use an own random generator for pageattr-test.c

[Andi Kleen]

On Tue, Mar 11, 2008 at 10:08:07PM +0100, Thomas Gleixner wrote:
> On Tue, 11 Mar 2008, Andi Kleen wrote:
> > > > > > Use an own random generator for pageattr-test.c
> > > > > > 
> > > > > > [Repost. Please ack/nack. This is a bug fix and imho a .25 late merge 
> > > > > > candidate because it fixes a subtle bug]
> > > > > 
> > > > > Care to point out which "subtle bug" is fixed ? 
> > > > > 
> > > > > You replace a random generator by another to get repeateable
> > > > > sequences. The non repeatability of the cpa test patterns is hardly a
> > > > > "subtle bug".
> > > > 
> > > > The subtle bug(s) are first that it is not repeatable (it really should),
> > > 
> > > As I said before. It's hardly a bug. In fact it is questionable
> > > whether fully reproducible test patterns are desired.
> > 
> > Ok then you won't be able to repeat the test ever.
> > 
> > I consider this bad practice in test code because it makes it impossible
> > to stabilize bugs
> 
> Test code with constant test patterns tend to miss the corner case
> bugs, while random pattern test cases hit them assumed that there is a
> broad enough tester base. 

The original idea was that there is enough variability in memory
maps that you still get the various scenarios tested, but that
a boot on a single machine stays deterministic in its behaviour.

> 
> It's a question of how you write such test code to achieve
> reproducability. It's not rocket science to track the variables of a
> test run and print them along with the printk, when a wrong state is
> detected. 

If you wanted to do that you would need some variant of my patch too --
to do it with random32() you would first need to print all NR_CPUS
state (and implement "kernel less" first for NR_CPUS > 128 kernels :),
then keep track of all CPUs the test thread ran on and print that
out too and also disable the regular timer reseeder to avoid races.
Clearly doesn't make sense.

random32() in lib/ is simply unusable as a deterministic RND,
it's more like super weak strange /dev/random variant which
probably should be never put into lib/ anyways because it's unlikely
to be generally useful.

So for a random but repeatable sequence like you describe you could keep the 
patch, replace the static int next = 1; with static int next and add a 
get_random_bytes(&next, sizeof(next)); and then print out the next value

-andi

Re: [PATCH REPOST for 2.6.25] Use an own random generator for pageattr-test.c

[Thomas Gleixner]

On Tue, 11 Mar 2008, Andi Kleen wrote:
> > It's a question of how you write such test code to achieve
> > reproducability. It's not rocket science to track the variables of a
> > test run and print them along with the printk, when a wrong state is
> > detected. 
> 
> If you wanted to do that you would need some variant of my patch too --
> to do it with random32() you would first need to print all NR_CPUS
> state (and implement "kernel less" first for NR_CPUS > 128 kernels :),
> then keep track of all CPUs the test thread ran on and print that
> out too and also disable the regular timer reseeder to avoid races.
> Clearly doesn't make sense.
> 
> random32() in lib/ is simply unusable as a deterministic RND,
> it's more like super weak strange /dev/random variant which
> probably should be never put into lib/ anyways because it's unlikely
> to be generally useful.
> 
> So for a random but repeatable sequence like you describe you could keep the 
> patch, replace the static int next = 1; with static int next and add a 
> get_random_bytes(&next, sizeof(next)); and then print out the next value

Oh well. Randomized test code is there to catch bugs by statistical
spreading. Having a pseudo randomized scenario which is repeatable per
machine is defeating the randomized approach. Repeating a test with a
stale pattern is pretty useless unless you catch a bug right in the
first run.

The only bug that code ever caught aside of tons of false positives
was when we increased the runtime length and added the thread which
repeated the test.

Finding a bug, when it was exposed by a static pattern, is trivial,
but the challenge is to make such tests useful enough with random
patterns. And there are ways to do that, e.g. by making the debug
output informative enough to provide information about the problem in
detail instead of printing some useless info "a != b".

Thanks,

	tglx

Re: [PATCH REPOST for 2.6.25] Use an own random generator for pageattr-test.c

[Andi Kleen]

> The only bug that code ever caught aside of tons of false positives

It caught bugs when I originally worked on cpa. However that 
had still the revert code and admittedly several were in 
that area (I'm still suspecting at some point you'll have
to readd that -- perhaps it'll be more useful for you then)

However I had originally a longer runtime length too, but later
decreased it when I sent out the patch (since i didn't want 
to submit another "rcu torture" which runs for hours...) 
Perhaps the result was a little too short too, that's possible.

> Finding a bug, when it was exposed by a static pattern, is trivial,
> but the challenge is to make such tests useful enough with random
> patterns. And there are ways to do that, e.g. by making the debug
> output informative enough to provide information about the problem in
> detail instead of printing some useless info "a != b".

Ok I admit I don't know how to do that effectively for cpa, but perhaps
you do.

-Andi