blackbird-op-linux/lib/reed_solomon, branch master

rslib: Make some functions static

2019-07-02T06:41:37+00:00

Fix sparse warnings: lib/reed_solomon/test_rslib.c:313:5: warning: symbol 'ex_rs_helper' was not declared. Should it be static? lib/reed_solomon/test_rslib.c:349:5: warning: symbol 'exercise_rs' was not declared. Should it be static? lib/reed_solomon/test_rslib.c:407:5: warning: symbol 'exercise_rs_bc' was not declared. Should it be static? Reported-by: Hulk Robot Signed-off-by: YueHaibing Signed-off-by: Thomas Gleixner Cc: Link: https://lkml.kernel.org/r/20190702061847.26060-1-yuehaibing@huawei.com

rslib: Fix remaining decoder flaws

2019-06-26T12:55:47+00:00

The decoder is flawed in the following ways: - The decoder sometimes fails silently, i.e. it announces success but returns a word that is not a codeword. - The return value of the decoder is incoherent with respect to how fixed erasures are counted. If the word to be decoded is a codeword, then the decoder always returns zero even if some erasures are given. On the other hand, if the word to be decoded contains errors, then the number of erasures is always included in the count of corrected symbols. So the decoder handles erasures without symbol corruption inconsistently. This inconsistency probably doesn't affect anyone using the decoder, but it is inconsistent with the documentation. - The error positions returned in eras_pos include all erasures, but the corrections are only set in the correction buffer if there actually is a symbol error. So if there are erasures without symbol corruption, then the correction buffer will contain errors (unless initialized to zero before calling the decoder) or some values will be unset (if the correction buffer is uninitialized). - When correcting data in-place the decoder does not correct errors in the parity. On the other hand, when returning the errors in correction buffers, errors in the parity are included. The respective fixed are: - The syndrome of a codeword is always zero, and the syndrome is linear, .i.e, S(x+e) = S(x) + S(e). So compute the syndrome for the error and check whether it equals the syndrome of the received word. If it does, then we have decoded to a valid codeword, otherwise we know that we have an uncorrectable error. Fortunately, some unrecoverable error conditions can be detected earlier in the decoding, which saves some processing power. - Simply count and return the number of symbols actually corrected. - Make sure to only return positions where symbols were corrected. - Also fix errors in parity when correcting in-place. Another option would be to completely disregard errors in the parity, but then the interface makes it impossible to write tests that test for silent failures. Other changes: - Only fill the correction buffer and error position buffer if both of them are provided. Otherwise correct in place. Previously the error position buffer was always populated with the positions of the corrected errors, irrespective of whether a correction buffer was supplied or not. The rationale for this change is that there seems to be two use cases for the decoder; correct in-place or use the correction buffers. The caller does not need the positions of the corrected errors when in-place correction is used. If in-place correction is not used, then both the correction buffer and error position buffer need to be populated. Signed-off-by: Ferdinand Blomqvist Signed-off-by: Thomas Gleixner Link: https://lkml.kernel.org/r/20190620141039.9874-8-ferdinand.blomqvist@gmail.com

rslib: Update documentation

2019-06-26T12:55:47+00:00

The decoder returns the number of corrected symbols, not bits. The caller provided syndrome must be in index form. Signed-off-by: Ferdinand Blomqvist Signed-off-by: Thomas Gleixner Link: https://lkml.kernel.org/r/20190620141039.9874-7-ferdinand.blomqvist@gmail.com

rslib: Fix handling of of caller provided syndrome

2019-06-26T12:55:47+00:00

Check if the syndrome provided by the caller is zero, and act accordingly. Signed-off-by: Ferdinand Blomqvist Signed-off-by: Thomas Gleixner Link: https://lkml.kernel.org/r/20190620141039.9874-6-ferdinand.blomqvist@gmail.com

rslib: decode_rs: Code cleanup

2019-06-26T12:55:46+00:00

Nothing useful was done after the finish label when count is negative so return directly instead of jumping to finish. Signed-off-by: Ferdinand Blomqvist Signed-off-by: Thomas Gleixner Link: https://lkml.kernel.org/r/20190620141039.9874-5-ferdinand.blomqvist@gmail.com

rslib: decode_rs: Fix length parameter check

2019-06-26T12:55:46+00:00

The length of the data load must be at least one. Or in other words, there must be room for at least 1 data and nroots parity symbols after shortening the RS code. Signed-off-by: Ferdinand Blomqvist Signed-off-by: Thomas Gleixner Link: https://lkml.kernel.org/r/20190620141039.9874-4-ferdinand.blomqvist@gmail.com

rslib: Fix decoding of shortened codes

2019-06-26T12:55:45+00:00

The decoding of shortenend codes is broken. It only works as expected if there are no erasures. When decoding with erasures, Lambda (the error and erasure locator polynomial) is initialized from the given erasure positions. The pad parameter is not accounted for by the initialisation code, and hence Lambda is initialized from incorrect erasure positions. The fix is to adjust the erasure positions by the supplied pad. Signed-off-by: Ferdinand Blomqvist Signed-off-by: Thomas Gleixner Link: https://lkml.kernel.org/r/20190620141039.9874-3-ferdinand.blomqvist@gmail.com

rslib: Add tests for the encoder and decoder

2019-06-26T12:55:45+00:00

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 Signed-off-by: Thomas Gleixner Link: https://lkml.kernel.org/r/20190620141039.9874-2-ferdinand.blomqvist@gmail.com

treewide: Add SPDX license identifier - Makefile/Kconfig

2019-05-21T08:50:46+00:00

Add SPDX license identifiers to all Make/Kconfig files which: - Have no license information of any form These files fall under the project license, GPL v2 only. The resulting SPDX license identifier is: GPL-2.0-only Signed-off-by: Thomas Gleixner Signed-off-by: Greg Kroah-Hartman

reed_solomon: Fix kernel-doc

2018-07-10T21:00:52+00:00

The current doc build warns: ./lib/reed_solomon/reed_solomon.c:287: WARNING: Unknown target name: "gfp". This is because it misinterprets the "GFP_" that is part of the description. Change the description to avoid the problem. Signed-off-by: Matthew Wilcox Acked-by: Kees Cook Signed-off-by: Jonathan Corbet