Use an own random generator for pageattr-test.c

PATCH In review Andi Kleen 3 participants 10 messages Mar 11, 2008

Subsystems (2)

x86 x86 MM

lore

Share & tools

lore

Andi Kleen

author

2008-03-11 01:30 UTC #0 lore raw

PATCH 1/1 Use an own random generator for pageattr-test.c

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 <[email protected]>

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

arch/x86/mm/pageattr-test.c +9 -2

Index: 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;

Andrew Morton

2008-03-11 02:40 UTC #1 lore raw

Quoted 4 lines · On Tue, 11 Mar 2008 02:30:14 +0100 Andi Kleen <[email protected]> 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.

Quoted 23 lines

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 <[email protected]>
---
 arch/x86/mm/pageattr-test.c |   11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)
Index: linux/arch/x86/mm/pageattr-test.c
===================================================================

arch/x86/mm/pageattr-test.c static int print_split(struct split_stat · line 110

Quoted 10 lines

arch/x86/mm/pageattr-test.c +7 -0

@@ -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().

Quoted 15 lines

arch/x86/mm/pageattr-test.c +1 -2

 /* 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;

Thomas Gleixner

2008-03-11 08:26 UTC #2 lore raw

In reply to Andi Kleen

Quoted 4 lines · 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]

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

Andi Kleen

author

2008-03-11 10:43 UTC #3 lore raw

Quoted 11 lines · Thomas Gleixner

Quoted 4 lines · 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]
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

Thomas Gleixner

2008-03-11 11:42 UTC #4 lore raw

Quoted 7 lines · Andi Kleen

Quoted 6 lines · Thomas Gleixner
Quoted 4 lines · 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]

Quoted 7 lines

Quoted 5 lines
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.

Quoted 3 lines

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

Andi Kleen

author

2008-03-11 11:46 UTC #5 lore raw

Quoted 13 lines · Thomas Gleixner

Quoted 9 lines · Andi Kleen
Quoted 8 lines · Thomas Gleixner
Quoted 4 lines · 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]
Care to point out which "subtle bug" is fixed ?

Quoted 8 lines

Quoted 5 lines
Quoted 3 lines
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.

Quoted 7 lines

Quoted 4 lines
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

Thomas Gleixner

2008-03-11 21:09 UTC #6 lore raw

Quoted 13 lines · Andi Kleen

Quoted 13 lines
Quoted 12 lines
Quoted 10 lines
Quoted 4 lines
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),

Quoted 7 lines

Quoted 2 lines
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.

Quoted 4 lines

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.

Quoted 9 lines

Quoted 6 lines
Quoted 3 lines
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

Andi Kleen

author

2008-03-11 21:47 UTC #7 lore raw

Quoted 17 lines · Thomas Gleixner

Quoted 16 lines · Andi Kleen
Quoted 15 lines
Quoted 5 lines
Quoted 5 lines
Quoted 4 lines
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]
Quoted 7 lines
Quoted 5 lines
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.

Quoted 8 lines

Quoted 4 lines
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.

Quoted 5 lines

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

Thomas Gleixner

2008-03-11 22:00 UTC #8 lore raw

Quoted 12 lines · Andi Kleen

Quoted 4 lines
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.

Quoted 8 lines

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

Andi Kleen

author

2008-03-11 22:09 UTC #9 lore raw

Quoted 1 line

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.

Quoted 5 lines

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