rslib: Add tests for the encoder and decoder

A Reed-Solomon code with minimum distance d can correct any error and
erasure pattern that satisfies 2 * #error + #erasures < d. If the
error correction capacity is exceeded, then correct decoding cannot be
guaranteed. The decoder must, however, return a valid codeword or report
failure.

There are two main tests:

- Check for correct behaviour up to the error correction capacity
- Check for correct behaviour beyond error corrupted capacity

Both tests are simple:

1. Generate random data
2. Encode data with the chosen code
3. Add errors and erasures to data
4. Decode the corrupted word
5. Check for correct behaviour

When testing up to capacity we test for:

- Correct decoding
- Correct return value (i.e. the number of corrected symbols)
- That the returned error positions are correct

There are two kinds of erasures; the erased symbol can be corrupted or
not. When counting the number of corrected symbols, erasures without
symbol corruption should not be counted. Similarly, the returned error
positions should only include positions where a correction is necessary.

We run the up to capacity tests for three different interfaces of
decode_rs:

- Use the correction buffers
- Use the correction buffers with syndromes provided by the caller
- Error correction in place (does not check the error positions)

When testing beyond capacity test for silent failures. A silent failure is
when the decoder returns success but the returned word is not a valid
codeword.

There are a couple of options for the tests:

- Verbosity.

- Whether to test for correct behaviour beyond capacity. Default is to
  test beyond capacity.

- Whether to allow erasures without symbol corruption. Defaults to yes.

Note that the tests take a couple of minutes to complete.

Signed-off-by: Ferdinand Blomqvist <ferdinand.blomqvist@gmail.com>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Link: https://lkml.kernel.org/r/20190620141039.9874-2-ferdinand.blomqvist@gmail.com

1 files changed, 12 insertions, 0 deletions

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index cbdfae379896..b0d71d9293dc 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1754,6 +1754,18 @@ config RBTREE_TEST
 	  A benchmark measuring the performance of the rbtree library.
 	  Also includes rbtree invariant checks.
 
+config REED_SOLOMON_TEST
+	tristate "Reed-Solomon library test"
+	depends on DEBUG_KERNEL || m
+	select REED_SOLOMON
+	select REED_SOLOMON_ENC16
+	select REED_SOLOMON_DEC16
+	help
+	  This option enables the self-test function of rslib at boot,
+	  or at module load time.
+
+	  If unsure, say N.
+
 config INTERVAL_TREE_TEST
 	tristate "Interval tree test"
 	depends on DEBUG_KERNEL