Linux-kselftest Archive on lore.kernel.org
 help / color / Atom feed
* [PATCH 0/4] deterministic random testing
@ 2020-10-25 21:48 Rasmus Villemoes
  2020-10-25 21:48 ` [PATCH 1/4] prandom.h: add *_state variant of prandom_u32_max Rasmus Villemoes
                   ` (4 more replies)
  0 siblings, 5 replies; 11+ messages in thread
From: Rasmus Villemoes @ 2020-10-25 21:48 UTC (permalink / raw)
  To: Shuah Khan, Kees Cook
  Cc: Petr Mladek, Willy Tarreau, linux-kselftest, linux-kernel,
	Arpitha Raghunandan, Andy Shevchenko, Brendan Higgins,
	Rasmus Villemoes

This is a bit of a mixed bag.

The background is that I have some sort() and list_sort() rework
planned, but as part of that series I want to extend their their test
suites somewhat to make sure I don't goof up - and I want to use lots
of random list lengths with random contents to increase the chance of
somebody eventually hitting "hey, sort() is broken when the length is
3 less than a power of 2 and only the last two elements are out of
order". But when such a case is hit, it's vitally important that the
developer can reproduce the exact same test case, which means using a
deterministic sequence of random numbers.

Since Petr noticed [1] the non-determinism in test_printf in
connection with Arpitha's work on rewriting it to kunit, this prompted
me to use test_printf as a first place to apply that principle, and
get the infrastructure in place that will avoid repeating the "module
parameter/seed the rnd_state/report the seed used" boilerplate in each
module.

Shuah, assuming the kselftest_module.h changes are ok, I think it's
most natural if you carry these patches, though I'd be happy with any
other route as well.

[1] https://lore.kernel.org/lkml/20200821113710.GA26290@alley/


Rasmus Villemoes (4):
  prandom.h: add *_state variant of prandom_u32_max
  kselftest_module.h: unconditionally expand the KSTM_MODULE_GLOBALS()
    macro
  kselftest_module.h: add struct rnd_state and seed parameter
  lib/test_printf.c: use deterministic sequence of random numbers

 Documentation/dev-tools/kselftest.rst      |  2 --
 include/linux/prandom.h                    | 29 ++++++++++++++++
 lib/test_bitmap.c                          |  3 --
 lib/test_printf.c                          | 13 ++++---
 lib/test_strscpy.c                         |  2 --
 tools/testing/selftests/kselftest_module.h | 40 ++++++++++++++++++----
 6 files changed, 72 insertions(+), 17 deletions(-)

-- 
2.23.0


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

* [PATCH 1/4] prandom.h: add *_state variant of prandom_u32_max
  2020-10-25 21:48 [PATCH 0/4] deterministic random testing Rasmus Villemoes
@ 2020-10-25 21:48 ` Rasmus Villemoes
  2020-10-30 16:00   ` Petr Mladek
  2020-10-25 21:48 ` [PATCH 2/4] kselftest_module.h: unconditionally expand the KSTM_MODULE_GLOBALS() macro Rasmus Villemoes
                   ` (3 subsequent siblings)
  4 siblings, 1 reply; 11+ messages in thread
From: Rasmus Villemoes @ 2020-10-25 21:48 UTC (permalink / raw)
  To: Shuah Khan, Kees Cook
  Cc: Petr Mladek, Willy Tarreau, linux-kselftest, linux-kernel,
	Arpitha Raghunandan, Andy Shevchenko, Brendan Higgins,
	Rasmus Villemoes

It is useful for test modules that make use of random numbers to allow
the exact same series of test cases to be repeated (e.g., after fixing
a bug in the code being tested). For that, the test module needs to
obtain its random numbers from a private state that can be seeded by a
known seed, e.g. given as a module parameter (and using a random seed
when that parameter is not given).

There's a few test modules I'm going to modify to follow that
scheme. As preparation, add a _state variant of the existing
prandom_u32_max(), and for convenience, also add a variant that
produces a value in a given range.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 include/linux/prandom.h | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)

diff --git a/include/linux/prandom.h b/include/linux/prandom.h
index aa16e6468f91e79e1f31..58ffcd56c705be34fb98 100644
--- a/include/linux/prandom.h
+++ b/include/linux/prandom.h
@@ -46,6 +46,35 @@ static inline u32 prandom_u32_max(u32 ep_ro)
 	return (u32)(((u64) prandom_u32() * ep_ro) >> 32);
 }
 
+/**
+ * prandom_u32_max_state - get pseudo-random number in internal [0, hi)
+ *
+ * Like prandom_u32_max, but use the given state structure.
+ * @state: pointer to state structure
+ * @hi: (exclusive) upper bound
+ *
+ * Exception: If @hi == 0, this returns 0.
+ */
+static inline u32 prandom_u32_max_state(struct rnd_state *state, u32 hi)
+{
+	return ((u64)prandom_u32_state(state) * hi) >> 32;
+}
+
+/**
+ * prandom_u32_range_state - get pseudo-random number in internal [lo, hi)
+ *
+ * @state: pointer to state structure
+ * @lo: (inclusive) lower bound
+ * @hi: (exclusive) upper bound
+ *
+ * Exception: If @lo == @hi, this returns @lo. Results are unspecified
+ * for @lo > @hi.
+ */
+static inline u32 prandom_u32_range_state(struct rnd_state *state, u32 lo, u32 hi)
+{
+	return lo + prandom_u32_max_state(state, hi - lo);
+}
+
 /*
  * Handle minimum values for seeds
  */
-- 
2.23.0


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

* [PATCH 2/4] kselftest_module.h: unconditionally expand the KSTM_MODULE_GLOBALS() macro
  2020-10-25 21:48 [PATCH 0/4] deterministic random testing Rasmus Villemoes
  2020-10-25 21:48 ` [PATCH 1/4] prandom.h: add *_state variant of prandom_u32_max Rasmus Villemoes
@ 2020-10-25 21:48 ` Rasmus Villemoes
  2020-10-30 16:02   ` Petr Mladek
  2020-10-25 21:48 ` [PATCH 3/4] kselftest_module.h: add struct rnd_state and seed parameter Rasmus Villemoes
                   ` (2 subsequent siblings)
  4 siblings, 1 reply; 11+ messages in thread
From: Rasmus Villemoes @ 2020-10-25 21:48 UTC (permalink / raw)
  To: Shuah Khan, Kees Cook
  Cc: Petr Mladek, Willy Tarreau, linux-kselftest, linux-kernel,
	Arpitha Raghunandan, Andy Shevchenko, Brendan Higgins,
	Rasmus Villemoes

Two out of three users of the kselftest_module.h header
manually define the failed_tests/total_tests variables instead of
making use of the KSTM_MODULE_GLOBALS() macro. However, instead of
just replacing those definitions with an invocation of that macro,
just unconditionally define them in the header file itself.

A coming change will add a few more global variables, and at least one
of those will be referenced from kstm_report() - however, that's not
possible currently, since when the definition is postponed until the
test module invokes KSTM_MODULE_GLOBALS(), the variable is not defined
by the time the compiler parses kstm_report().

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 Documentation/dev-tools/kselftest.rst      | 2 --
 lib/test_bitmap.c                          | 3 ---
 lib/test_printf.c                          | 2 --
 lib/test_strscpy.c                         | 2 --
 tools/testing/selftests/kselftest_module.h | 5 ++---
 5 files changed, 2 insertions(+), 12 deletions(-)

diff --git a/Documentation/dev-tools/kselftest.rst b/Documentation/dev-tools/kselftest.rst
index a901def730d95ca4c2c1..9899e86ed470ae527fdc 100644
--- a/Documentation/dev-tools/kselftest.rst
+++ b/Documentation/dev-tools/kselftest.rst
@@ -281,8 +281,6 @@ A bare bones test module might look like this:
 
    #include "../tools/testing/selftests/kselftest/module.h"
 
-   KSTM_MODULE_GLOBALS();
-
    /*
     * Kernel module for testing the foobinator
     */
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 4425a1dd4ef1c7d85973..02fc667a9b3d5d7de7eb 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -16,9 +16,6 @@
 
 #include "../tools/testing/selftests/kselftest_module.h"
 
-static unsigned total_tests __initdata;
-static unsigned failed_tests __initdata;
-
 static char pbl_buffer[PAGE_SIZE] __initdata;
 
 static const unsigned long exp1[] __initconst = {
diff --git a/lib/test_printf.c b/lib/test_printf.c
index 7ac87f18a10ff8209ad5..1ed4a27390cb621715ab 100644
--- a/lib/test_printf.c
+++ b/lib/test_printf.c
@@ -30,8 +30,6 @@
 #define PAD_SIZE 16
 #define FILL_CHAR '$'
 
-static unsigned total_tests __initdata;
-static unsigned failed_tests __initdata;
 static char *test_buffer __initdata;
 static char *alloced_buffer __initdata;
 
diff --git a/lib/test_strscpy.c b/lib/test_strscpy.c
index a827f94601f5d945b163..be477a52d87185ee6a01 100644
--- a/lib/test_strscpy.c
+++ b/lib/test_strscpy.c
@@ -10,8 +10,6 @@
  * Kernel module for testing 'strscpy' family of functions.
  */
 
-KSTM_MODULE_GLOBALS();
-
 /*
  * tc() - Run a specific test case.
  * @src: Source string, argument to strscpy_pad()
diff --git a/tools/testing/selftests/kselftest_module.h b/tools/testing/selftests/kselftest_module.h
index e8eafaf0941aa716d9dc..c81c0b0c054befaf665b 100644
--- a/tools/testing/selftests/kselftest_module.h
+++ b/tools/testing/selftests/kselftest_module.h
@@ -9,9 +9,8 @@
  * See Documentation/dev-tools/kselftest.rst for an example test module.
  */
 
-#define KSTM_MODULE_GLOBALS()			\
-static unsigned int total_tests __initdata;	\
-static unsigned int failed_tests __initdata
+static unsigned int total_tests __initdata;
+static unsigned int failed_tests __initdata;
 
 #define KSTM_CHECK_ZERO(x) do {						\
 	total_tests++;							\
-- 
2.23.0


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

* [PATCH 3/4] kselftest_module.h: add struct rnd_state and seed parameter
  2020-10-25 21:48 [PATCH 0/4] deterministic random testing Rasmus Villemoes
  2020-10-25 21:48 ` [PATCH 1/4] prandom.h: add *_state variant of prandom_u32_max Rasmus Villemoes
  2020-10-25 21:48 ` [PATCH 2/4] kselftest_module.h: unconditionally expand the KSTM_MODULE_GLOBALS() macro Rasmus Villemoes
@ 2020-10-25 21:48 ` Rasmus Villemoes
  2020-10-30 16:23   ` Petr Mladek
  2020-10-25 21:48 ` [PATCH 4/4] lib/test_printf.c: use deterministic sequence of random numbers Rasmus Villemoes
  2020-10-26 10:59 ` [PATCH 0/4] deterministic random testing Andy Shevchenko
  4 siblings, 1 reply; 11+ messages in thread
From: Rasmus Villemoes @ 2020-10-25 21:48 UTC (permalink / raw)
  To: Shuah Khan, Kees Cook
  Cc: Petr Mladek, Willy Tarreau, linux-kselftest, linux-kernel,
	Arpitha Raghunandan, Andy Shevchenko, Brendan Higgins,
	Rasmus Villemoes

Some test suites make use of random numbers to increase the test
coverage when the test suite gets run on different machines and
increase the chance of some corner case bug being discovered - and I'm
planning on extending some existing ones in that direction as
well. However, should a bug be found this way, it's important that the
exact same series of tests can be repeated to verify the bug is
fixed. That means the random numbers must be obtained
deterministically from a generator private to the test module.

To avoid adding boilerplate to various test modules, put some logic
into kselftest_module.h: If the module declares that it will use
random numbers, add a "seed" module parameter. If not explicitly given
when the module is loaded (or via kernel command line), obtain a
random one. In either case, print the seed used, and repeat that
information if there was at least one test failing.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 tools/testing/selftests/kselftest_module.h | 35 ++++++++++++++++++++--
 1 file changed, 32 insertions(+), 3 deletions(-)

diff --git a/tools/testing/selftests/kselftest_module.h b/tools/testing/selftests/kselftest_module.h
index c81c0b0c054befaf665b..43f3ca58fcd550b8ac83 100644
--- a/tools/testing/selftests/kselftest_module.h
+++ b/tools/testing/selftests/kselftest_module.h
@@ -3,14 +3,31 @@
 #define __KSELFTEST_MODULE_H
 
 #include <linux/module.h>
+#include <linux/prandom.h>
+#include <linux/random.h>
 
 /*
  * Test framework for writing test modules to be loaded by kselftest.
  * See Documentation/dev-tools/kselftest.rst for an example test module.
  */
 
+/*
+ * If the test module makes use of random numbers, define KSTM_RANDOM
+ * to 1 before including this header. Then a module parameter "seed"
+ * will be defined. If not given, a random one will be obtained. In
+ * either case, the used seed is reported, so the exact same series of
+ * tests can be repeated by loading the module with that seed
+ * given.
+ */
+
+#ifndef KSTM_RANDOM
+#define KSTM_RANDOM 0
+#endif
+
 static unsigned int total_tests __initdata;
 static unsigned int failed_tests __initdata;
+static struct rnd_state rnd_state __initdata;
+static u64 seed __initdata;
 
 #define KSTM_CHECK_ZERO(x) do {						\
 	total_tests++;							\
@@ -22,11 +39,13 @@ static unsigned int failed_tests __initdata;
 
 static inline int kstm_report(unsigned int total_tests, unsigned int failed_tests)
 {
-	if (failed_tests == 0)
+	if (failed_tests == 0) {
 		pr_info("all %u tests passed\n", total_tests);
-	else
+	} else {
 		pr_warn("failed %u out of %u tests\n", failed_tests, total_tests);
-
+		if (KSTM_RANDOM)
+			pr_info("random seed used was 0x%016llx\n", seed);
+	}
 	return failed_tests ? -EINVAL : 0;
 }
 
@@ -34,6 +53,12 @@ static inline int kstm_report(unsigned int total_tests, unsigned int failed_test
 static int __init __module##_init(void)			\
 {							\
 	pr_info("loaded.\n");				\
+	if (KSTM_RANDOM) {				\
+		if (!seed)				\
+			seed = get_random_u64();	\
+		prandom_seed_state(&rnd_state, seed);	\
+		pr_info("random seed = 0x%016llx\n", seed);	\
+	}						\
 	selftest();					\
 	return kstm_report(total_tests, failed_tests);	\
 }							\
@@ -44,4 +69,8 @@ static void __exit __module##_exit(void)		\
 module_init(__module##_init);				\
 module_exit(__module##_exit)
 
+#if KSTM_RANDOM
+module_param(seed, ullong, 0444);
+#endif
+
 #endif	/* __KSELFTEST_MODULE_H */
-- 
2.23.0


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

* [PATCH 4/4] lib/test_printf.c: use deterministic sequence of random numbers
  2020-10-25 21:48 [PATCH 0/4] deterministic random testing Rasmus Villemoes
                   ` (2 preceding siblings ...)
  2020-10-25 21:48 ` [PATCH 3/4] kselftest_module.h: add struct rnd_state and seed parameter Rasmus Villemoes
@ 2020-10-25 21:48 ` Rasmus Villemoes
  2020-10-30 16:26   ` Petr Mladek
  2020-10-26 10:59 ` [PATCH 0/4] deterministic random testing Andy Shevchenko
  4 siblings, 1 reply; 11+ messages in thread
From: Rasmus Villemoes @ 2020-10-25 21:48 UTC (permalink / raw)
  To: Shuah Khan, Kees Cook
  Cc: Petr Mladek, Willy Tarreau, linux-kselftest, linux-kernel,
	Arpitha Raghunandan, Andy Shevchenko, Brendan Higgins,
	Rasmus Villemoes

The printf test suite does each test with a few different buffer sizes
to ensure vsnprintf() behaves correctly with respect to truncation and
size reporting. It calls vsnprintf() with a buffer size that is
guaranteed to be big enough, a buffer size of 0 to ensure that nothing
gets written to the buffer, but it also calls vsnprintf() with a
buffer size chosen to guarantee the output gets truncated somewhere in
the middle.

That buffer size is chosen randomly to increase the chance of finding
some corner case bug (for example, there used to be some %p<foo>
extension that would fail to produce any output if there wasn't room
enough for it all, despite the requirement of producing as much as
there's room for). I'm not aware of that having found anything yet,
but should it happen, it's annoying not to be able to repeat the
test with the same sequence of truncated lengths.

For demonstration purposes, if we break one of the test cases
deliberately, we still get different buffer sizes if we don't pass the
seed parameter:

root@(none):/# modprobe test_printf
[   15.317783] test_printf: vsnprintf(buf, 18, "%piS|%pIS", ...) wrote '127.000.000.001|1', expected '127-000.000.001|1'
[   15.323182] test_printf: failed 3 out of 388 tests
[   15.324034] test_printf: random seed used was 0x278bb9311979cc91
modprobe: ERROR: could not insert 'test_printf': Invalid argument

root@(none):/# modprobe test_printf
[   13.940909] test_printf: vsnprintf(buf, 22, "%piS|%pIS", ...) wrote '127.000.000.001|127.0', expected '127-000.000.001|127.0'
[   13.944744] test_printf: failed 3 out of 388 tests
[   13.945607] test_printf: random seed used was 0x9f72eee1c9dc02e5
modprobe: ERROR: could not insert 'test_printf': Invalid argument

but to repeat a specific sequence of tests, we can do

root@(none):/# modprobe test_printf seed=0x9f72eee1c9dc02e5
[  448.328685] test_printf: vsnprintf(buf, 22, "%piS|%pIS", ...) wrote '127.000.000.001|127.0', expected '127-000.000.001|127.0'
[  448.331650] test_printf: failed 3 out of 388 tests
[  448.332295] test_printf: random seed used was 0x9f72eee1c9dc02e5
modprobe: ERROR: could not insert 'test_printf': Invalid argument

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/test_printf.c | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

diff --git a/lib/test_printf.c b/lib/test_printf.c
index 1ed4a27390cb621715ab..bbea8b807d1eafe67e01 100644
--- a/lib/test_printf.c
+++ b/lib/test_printf.c
@@ -24,6 +24,7 @@
 
 #include <linux/property.h>
 
+#define KSTM_RANDOM 1
 #include "../tools/testing/selftests/kselftest_module.h"
 
 #define BUF_SIZE 256
@@ -111,8 +112,14 @@ __test(const char *expect, int elen, const char *fmt, ...)
 	 * be able to print it as expected.
 	 */
 	failed_tests += do_test(BUF_SIZE, expect, elen, fmt, ap);
-	rand = 1 + prandom_u32_max(elen+1);
-	/* Since elen < BUF_SIZE, we have 1 <= rand <= BUF_SIZE. */
+	rand = prandom_u32_range_state(&rnd_state, 1, elen + 1);
+	/*
+	 * Except for elen == 0, we have 1 <= rand <= elen < BUF_SIZE,
+	 * i.e., the output is guaranteed to be truncated somewhere in
+	 * the middle, and we're not pretending the buffer to be
+	 * larger than it really is. For the boring case of elen == 0,
+	 * rand is 1, which is of course also <= BUF_SIZE.
+	 */
 	failed_tests += do_test(rand, expect, elen, fmt, ap);
 	failed_tests += do_test(0, expect, elen, fmt, ap);
 
-- 
2.23.0


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

* Re: [PATCH 0/4] deterministic random testing
  2020-10-25 21:48 [PATCH 0/4] deterministic random testing Rasmus Villemoes
                   ` (3 preceding siblings ...)
  2020-10-25 21:48 ` [PATCH 4/4] lib/test_printf.c: use deterministic sequence of random numbers Rasmus Villemoes
@ 2020-10-26 10:59 ` Andy Shevchenko
  2020-10-30 12:58   ` Rasmus Villemoes
  4 siblings, 1 reply; 11+ messages in thread
From: Andy Shevchenko @ 2020-10-26 10:59 UTC (permalink / raw)
  To: Rasmus Villemoes
  Cc: Shuah Khan, Kees Cook, Petr Mladek, Willy Tarreau,
	linux-kselftest, linux-kernel, Arpitha Raghunandan,
	Brendan Higgins

On Sun, Oct 25, 2020 at 10:48:38PM +0100, Rasmus Villemoes wrote:
> This is a bit of a mixed bag.
> 
> The background is that I have some sort() and list_sort() rework
> planned, but as part of that series I want to extend their their test
> suites somewhat to make sure I don't goof up - and I want to use lots
> of random list lengths with random contents to increase the chance of
> somebody eventually hitting "hey, sort() is broken when the length is
> 3 less than a power of 2 and only the last two elements are out of
> order". But when such a case is hit, it's vitally important that the
> developer can reproduce the exact same test case, which means using a
> deterministic sequence of random numbers.
> 
> Since Petr noticed [1] the non-determinism in test_printf in
> connection with Arpitha's work on rewriting it to kunit, this prompted
> me to use test_printf as a first place to apply that principle, and
> get the infrastructure in place that will avoid repeating the "module
> parameter/seed the rnd_state/report the seed used" boilerplate in each
> module.
> 
> Shuah, assuming the kselftest_module.h changes are ok, I think it's
> most natural if you carry these patches, though I'd be happy with any
> other route as well.

Completely in favour of this.

Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>

One note though. AFAIU the global variables are always being used in the
modules that include the corresponding header. Otherwise we might have an extra
warning(s). I believe you have compiled with W=1 to exclude other cases.

> [1] https://lore.kernel.org/lkml/20200821113710.GA26290@alley/
> 
> 
> Rasmus Villemoes (4):
>   prandom.h: add *_state variant of prandom_u32_max
>   kselftest_module.h: unconditionally expand the KSTM_MODULE_GLOBALS()
>     macro
>   kselftest_module.h: add struct rnd_state and seed parameter
>   lib/test_printf.c: use deterministic sequence of random numbers
> 
>  Documentation/dev-tools/kselftest.rst      |  2 --
>  include/linux/prandom.h                    | 29 ++++++++++++++++
>  lib/test_bitmap.c                          |  3 --
>  lib/test_printf.c                          | 13 ++++---
>  lib/test_strscpy.c                         |  2 --
>  tools/testing/selftests/kselftest_module.h | 40 ++++++++++++++++++----
>  6 files changed, 72 insertions(+), 17 deletions(-)
> 
> -- 
> 2.23.0
> 

-- 
With Best Regards,
Andy Shevchenko



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

* Re: [PATCH 0/4] deterministic random testing
  2020-10-26 10:59 ` [PATCH 0/4] deterministic random testing Andy Shevchenko
@ 2020-10-30 12:58   ` Rasmus Villemoes
  0 siblings, 0 replies; 11+ messages in thread
From: Rasmus Villemoes @ 2020-10-30 12:58 UTC (permalink / raw)
  To: Andy Shevchenko
  Cc: Shuah Khan, Kees Cook, Petr Mladek, Willy Tarreau,
	linux-kselftest, linux-kernel, Arpitha Raghunandan,
	Brendan Higgins

On 26/10/2020 11.59, Andy Shevchenko wrote:
> On Sun, Oct 25, 2020 at 10:48:38PM +0100, Rasmus Villemoes wrote:
>> This is a bit of a mixed bag.
>>
>> The background is that I have some sort() and list_sort() rework
>> planned, but as part of that series I want to extend their their test
>> suites somewhat to make sure I don't goof up - and I want to use lots
>> of random list lengths with random contents to increase the chance of
>> somebody eventually hitting "hey, sort() is broken when the length is
>> 3 less than a power of 2 and only the last two elements are out of
>> order". But when such a case is hit, it's vitally important that the
>> developer can reproduce the exact same test case, which means using a
>> deterministic sequence of random numbers.
>>
>> Since Petr noticed [1] the non-determinism in test_printf in
>> connection with Arpitha's work on rewriting it to kunit, this prompted
>> me to use test_printf as a first place to apply that principle, and
>> get the infrastructure in place that will avoid repeating the "module
>> parameter/seed the rnd_state/report the seed used" boilerplate in each
>> module.
>>
>> Shuah, assuming the kselftest_module.h changes are ok, I think it's
>> most natural if you carry these patches, though I'd be happy with any
>> other route as well.
> 
> Completely in favour of this.
> 
> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>

Thanks.

> One note though. AFAIU the global variables are always being used in the
> modules that include the corresponding header. Otherwise we might have an extra
> warning(s). I believe you have compiled with W=1 to exclude other cases.

Yes, I unconditionally define the two new variables. gcc doesn't warn
about them being unused, since they are referenced from inside a

  if (0) {}

block. And when those references are the only ones, gcc is smart enough
to elide the static variables completely, so they don't even take up
space in .data (or .init.data) - you can verify by running nm on
test_printf.o and test_bitmap.o - the former has 'seed' and 'rnd_state'
symbols, the latter does not.

I did it that way to reduce the need for explicit preprocessor
conditionals inside C functions.

Rasmus

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

* Re: [PATCH 1/4] prandom.h: add *_state variant of prandom_u32_max
  2020-10-25 21:48 ` [PATCH 1/4] prandom.h: add *_state variant of prandom_u32_max Rasmus Villemoes
@ 2020-10-30 16:00   ` Petr Mladek
  0 siblings, 0 replies; 11+ messages in thread
From: Petr Mladek @ 2020-10-30 16:00 UTC (permalink / raw)
  To: Rasmus Villemoes
  Cc: Shuah Khan, Kees Cook, Willy Tarreau, linux-kselftest,
	linux-kernel, Arpitha Raghunandan, Andy Shevchenko,
	Brendan Higgins

On Sun 2020-10-25 22:48:39, Rasmus Villemoes wrote:
> It is useful for test modules that make use of random numbers to allow
> the exact same series of test cases to be repeated (e.g., after fixing
> a bug in the code being tested). For that, the test module needs to
> obtain its random numbers from a private state that can be seeded by a
> known seed, e.g. given as a module parameter (and using a random seed
> when that parameter is not given).
> 
> There's a few test modules I'm going to modify to follow that
> scheme. As preparation, add a _state variant of the existing
> prandom_u32_max(), and for convenience, also add a variant that
> produces a value in a given range.
> 
> Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> ---
>  include/linux/prandom.h | 29 +++++++++++++++++++++++++++++
>  1 file changed, 29 insertions(+)
> 
> diff --git a/include/linux/prandom.h b/include/linux/prandom.h
> index aa16e6468f91e79e1f31..58ffcd56c705be34fb98 100644
> --- a/include/linux/prandom.h
> +++ b/include/linux/prandom.h
> @@ -46,6 +46,35 @@ static inline u32 prandom_u32_max(u32 ep_ro)
>  	return (u32)(((u64) prandom_u32() * ep_ro) >> 32);
>  }
>  
> +/**
> + * prandom_u32_max_state - get pseudo-random number in internal [0, hi)

s/internal/interval/

> + *
> + * Like prandom_u32_max, but use the given state structure.
> + * @state: pointer to state structure
> + * @hi: (exclusive) upper bound
> + *
> + * Exception: If @hi == 0, this returns 0.
> + */
> +static inline u32 prandom_u32_max_state(struct rnd_state *state, u32 hi)
> +{
> +	return ((u64)prandom_u32_state(state) * hi) >> 32;
> +}
> +
> +/**
> + * prandom_u32_range_state - get pseudo-random number in internal [lo, hi)

same here

> + *
> + * @state: pointer to state structure
> + * @lo: (inclusive) lower bound
> + * @hi: (exclusive) upper bound
> + *
> + * Exception: If @lo == @hi, this returns @lo. Results are unspecified
> + * for @lo > @hi.
> + */
> +static inline u32 prandom_u32_range_state(struct rnd_state *state, u32 lo, u32 hi)
> +{
> +	return lo + prandom_u32_max_state(state, hi - lo);
> +}

With the above typo fixes:

Reviewed-by: Petr Mladek <pmladek@suse.com>

Well, I guess that we need ack from Willy.

Best Regards,
Petr

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

* Re: [PATCH 2/4] kselftest_module.h: unconditionally expand the KSTM_MODULE_GLOBALS() macro
  2020-10-25 21:48 ` [PATCH 2/4] kselftest_module.h: unconditionally expand the KSTM_MODULE_GLOBALS() macro Rasmus Villemoes
@ 2020-10-30 16:02   ` Petr Mladek
  0 siblings, 0 replies; 11+ messages in thread
From: Petr Mladek @ 2020-10-30 16:02 UTC (permalink / raw)
  To: Rasmus Villemoes
  Cc: Shuah Khan, Kees Cook, Willy Tarreau, linux-kselftest,
	linux-kernel, Arpitha Raghunandan, Andy Shevchenko,
	Brendan Higgins

On Sun 2020-10-25 22:48:40, Rasmus Villemoes wrote:
> Two out of three users of the kselftest_module.h header
> manually define the failed_tests/total_tests variables instead of
> making use of the KSTM_MODULE_GLOBALS() macro. However, instead of
> just replacing those definitions with an invocation of that macro,
> just unconditionally define them in the header file itself.
> 
> A coming change will add a few more global variables, and at least one
> of those will be referenced from kstm_report() - however, that's not
> possible currently, since when the definition is postponed until the
> test module invokes KSTM_MODULE_GLOBALS(), the variable is not defined
> by the time the compiler parses kstm_report().
> 
> Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>

Reviewed-by: Petr Mladek <pmladek@suse.com>

Best Regards,
Petr

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

* Re: [PATCH 3/4] kselftest_module.h: add struct rnd_state and seed parameter
  2020-10-25 21:48 ` [PATCH 3/4] kselftest_module.h: add struct rnd_state and seed parameter Rasmus Villemoes
@ 2020-10-30 16:23   ` Petr Mladek
  0 siblings, 0 replies; 11+ messages in thread
From: Petr Mladek @ 2020-10-30 16:23 UTC (permalink / raw)
  To: Rasmus Villemoes
  Cc: Shuah Khan, Kees Cook, Willy Tarreau, linux-kselftest,
	linux-kernel, Arpitha Raghunandan, Andy Shevchenko,
	Brendan Higgins

On Sun 2020-10-25 22:48:41, Rasmus Villemoes wrote:
> Some test suites make use of random numbers to increase the test
> coverage when the test suite gets run on different machines and
> increase the chance of some corner case bug being discovered - and I'm
> planning on extending some existing ones in that direction as
> well. However, should a bug be found this way, it's important that the
> exact same series of tests can be repeated to verify the bug is
> fixed. That means the random numbers must be obtained
> deterministically from a generator private to the test module.
> 
> To avoid adding boilerplate to various test modules, put some logic
> into kselftest_module.h: If the module declares that it will use
> random numbers, add a "seed" module parameter. If not explicitly given
> when the module is loaded (or via kernel command line), obtain a
> random one. In either case, print the seed used, and repeat that
> information if there was at least one test failing.
> 
> Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> ---
>  tools/testing/selftests/kselftest_module.h | 35 ++++++++++++++++++++--
>  1 file changed, 32 insertions(+), 3 deletions(-)
> 
> diff --git a/tools/testing/selftests/kselftest_module.h b/tools/testing/selftests/kselftest_module.h
> index c81c0b0c054befaf665b..43f3ca58fcd550b8ac83 100644
> --- a/tools/testing/selftests/kselftest_module.h
> +++ b/tools/testing/selftests/kselftest_module.h
> @@ -3,14 +3,31 @@
>  #define __KSELFTEST_MODULE_H
>  
>  #include <linux/module.h>
> +#include <linux/prandom.h>
> +#include <linux/random.h>
>  
>  /*
>   * Test framework for writing test modules to be loaded by kselftest.
>   * See Documentation/dev-tools/kselftest.rst for an example test module.
>   */
>  
> +/*
> + * If the test module makes use of random numbers, define KSTM_RANDOM
> + * to 1 before including this header. Then a module parameter "seed"
> + * will be defined. If not given, a random one will be obtained. In
> + * either case, the used seed is reported, so the exact same series of
> + * tests can be repeated by loading the module with that seed
> + * given.
> + */
> +
> +#ifndef KSTM_RANDOM
> +#define KSTM_RANDOM 0
> +#endif
> +
>  static unsigned int total_tests __initdata;
>  static unsigned int failed_tests __initdata;
> +static struct rnd_state rnd_state __initdata;
> +static u64 seed __initdata;
>  
>  #define KSTM_CHECK_ZERO(x) do {						\
>  	total_tests++;							\
> @@ -22,11 +39,13 @@ static unsigned int failed_tests __initdata;
>  
>  static inline int kstm_report(unsigned int total_tests, unsigned int failed_tests)
>  {
> -	if (failed_tests == 0)
> +	if (failed_tests == 0) {
>  		pr_info("all %u tests passed\n", total_tests);
> -	else
> +	} else {
>  		pr_warn("failed %u out of %u tests\n", failed_tests, total_tests);
> -
> +		if (KSTM_RANDOM)
> +			pr_info("random seed used was 0x%016llx\n", seed);

I have a bit mixed feelings about this. It is genial and dirty hack at the
same time ;-) Well, it is basically the same approach as with
IS_ENABLED(CONFIG_bla_bla).

Reviewed-by: Petr Mladek <pmladek@suse.com>

Best Regards,
Petr

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

* Re: [PATCH 4/4] lib/test_printf.c: use deterministic sequence of random numbers
  2020-10-25 21:48 ` [PATCH 4/4] lib/test_printf.c: use deterministic sequence of random numbers Rasmus Villemoes
@ 2020-10-30 16:26   ` Petr Mladek
  0 siblings, 0 replies; 11+ messages in thread
From: Petr Mladek @ 2020-10-30 16:26 UTC (permalink / raw)
  To: Rasmus Villemoes
  Cc: Shuah Khan, Kees Cook, Willy Tarreau, linux-kselftest,
	linux-kernel, Arpitha Raghunandan, Andy Shevchenko,
	Brendan Higgins

On Sun 2020-10-25 22:48:42, Rasmus Villemoes wrote:
> The printf test suite does each test with a few different buffer sizes
> to ensure vsnprintf() behaves correctly with respect to truncation and
> size reporting. It calls vsnprintf() with a buffer size that is
> guaranteed to be big enough, a buffer size of 0 to ensure that nothing
> gets written to the buffer, but it also calls vsnprintf() with a
> buffer size chosen to guarantee the output gets truncated somewhere in
> the middle.
> 
> That buffer size is chosen randomly to increase the chance of finding
> some corner case bug (for example, there used to be some %p<foo>
> extension that would fail to produce any output if there wasn't room
> enough for it all, despite the requirement of producing as much as
> there's room for). I'm not aware of that having found anything yet,
> but should it happen, it's annoying not to be able to repeat the
> test with the same sequence of truncated lengths.
> 
> For demonstration purposes, if we break one of the test cases
> deliberately, we still get different buffer sizes if we don't pass the
> seed parameter:
> 
> root@(none):/# modprobe test_printf
> [   15.317783] test_printf: vsnprintf(buf, 18, "%piS|%pIS", ...) wrote '127.000.000.001|1', expected '127-000.000.001|1'
> [   15.323182] test_printf: failed 3 out of 388 tests
> [   15.324034] test_printf: random seed used was 0x278bb9311979cc91
> modprobe: ERROR: could not insert 'test_printf': Invalid argument
> 
> root@(none):/# modprobe test_printf
> [   13.940909] test_printf: vsnprintf(buf, 22, "%piS|%pIS", ...) wrote '127.000.000.001|127.0', expected '127-000.000.001|127.0'
> [   13.944744] test_printf: failed 3 out of 388 tests
> [   13.945607] test_printf: random seed used was 0x9f72eee1c9dc02e5
> modprobe: ERROR: could not insert 'test_printf': Invalid argument
> 
> but to repeat a specific sequence of tests, we can do
> 
> root@(none):/# modprobe test_printf seed=0x9f72eee1c9dc02e5
> [  448.328685] test_printf: vsnprintf(buf, 22, "%piS|%pIS", ...) wrote '127.000.000.001|127.0', expected '127-000.000.001|127.0'
> [  448.331650] test_printf: failed 3 out of 388 tests
> [  448.332295] test_printf: random seed used was 0x9f72eee1c9dc02e5
> modprobe: ERROR: could not insert 'test_printf': Invalid argument
> 
> Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>

Great feature!

Reviewed-by: Petr Mladek <pmladek@suse.com>

Best Regards,
Petr

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

end of thread, back to index

Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-10-25 21:48 [PATCH 0/4] deterministic random testing Rasmus Villemoes
2020-10-25 21:48 ` [PATCH 1/4] prandom.h: add *_state variant of prandom_u32_max Rasmus Villemoes
2020-10-30 16:00   ` Petr Mladek
2020-10-25 21:48 ` [PATCH 2/4] kselftest_module.h: unconditionally expand the KSTM_MODULE_GLOBALS() macro Rasmus Villemoes
2020-10-30 16:02   ` Petr Mladek
2020-10-25 21:48 ` [PATCH 3/4] kselftest_module.h: add struct rnd_state and seed parameter Rasmus Villemoes
2020-10-30 16:23   ` Petr Mladek
2020-10-25 21:48 ` [PATCH 4/4] lib/test_printf.c: use deterministic sequence of random numbers Rasmus Villemoes
2020-10-30 16:26   ` Petr Mladek
2020-10-26 10:59 ` [PATCH 0/4] deterministic random testing Andy Shevchenko
2020-10-30 12:58   ` Rasmus Villemoes

Linux-kselftest Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-kselftest/0 linux-kselftest/git/0.git

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

Example config snippet for mirrors

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


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