| Message ID | 20201025214842.5924-1-linux@rasmusvillemoes.dk |
|---|---|
| Headers | show |
| Series | deterministic random testing | expand |
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 >
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
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
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
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
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(-)