02 Jul, 2019
1 commit
-
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
26 Jun, 2019
7 commits
-
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 -
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 -
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 -
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 -
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 -
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 -
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 capacityBoth 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 behaviourWhen 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 correctThere 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
21 May, 2019
1 commit
-
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
11 Jul, 2018
1 commit
-
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
13 Jun, 2018
1 commit
-
The kmalloc() function has a 2-factor argument form, kmalloc_array(). This
patch replaces cases of:kmalloc(a * b, gfp)
with:
kmalloc_array(a * b, gfp)as well as handling cases of:
kmalloc(a * b * c, gfp)
with:
kmalloc(array3_size(a, b, c), gfp)
as it's slightly less ugly than:
kmalloc_array(array_size(a, b), c, gfp)
This does, however, attempt to ignore constant size factors like:
kmalloc(4 * 1024, gfp)
though any constants defined via macros get caught up in the conversion.
Any factors with a sizeof() of "unsigned char", "char", and "u8" were
dropped, since they're redundant.The tools/ directory was manually excluded, since it has its own
implementation of kmalloc().The Coccinelle script used for this was:
// Fix redundant parens around sizeof().
@@
type TYPE;
expression THING, E;
@@(
kmalloc(
- (sizeof(TYPE)) * E
+ sizeof(TYPE) * E
, ...)
|
kmalloc(
- (sizeof(THING)) * E
+ sizeof(THING) * E
, ...)
)// Drop single-byte sizes and redundant parens.
@@
expression COUNT;
typedef u8;
typedef __u8;
@@(
kmalloc(
- sizeof(u8) * (COUNT)
+ COUNT
, ...)
|
kmalloc(
- sizeof(__u8) * (COUNT)
+ COUNT
, ...)
|
kmalloc(
- sizeof(char) * (COUNT)
+ COUNT
, ...)
|
kmalloc(
- sizeof(unsigned char) * (COUNT)
+ COUNT
, ...)
|
kmalloc(
- sizeof(u8) * COUNT
+ COUNT
, ...)
|
kmalloc(
- sizeof(__u8) * COUNT
+ COUNT
, ...)
|
kmalloc(
- sizeof(char) * COUNT
+ COUNT
, ...)
|
kmalloc(
- sizeof(unsigned char) * COUNT
+ COUNT
, ...)
)// 2-factor product with sizeof(type/expression) and identifier or constant.
@@
type TYPE;
expression THING;
identifier COUNT_ID;
constant COUNT_CONST;
@@(
- kmalloc
+ kmalloc_array
(
- sizeof(TYPE) * (COUNT_ID)
+ COUNT_ID, sizeof(TYPE)
, ...)
|
- kmalloc
+ kmalloc_array
(
- sizeof(TYPE) * COUNT_ID
+ COUNT_ID, sizeof(TYPE)
, ...)
|
- kmalloc
+ kmalloc_array
(
- sizeof(TYPE) * (COUNT_CONST)
+ COUNT_CONST, sizeof(TYPE)
, ...)
|
- kmalloc
+ kmalloc_array
(
- sizeof(TYPE) * COUNT_CONST
+ COUNT_CONST, sizeof(TYPE)
, ...)
|
- kmalloc
+ kmalloc_array
(
- sizeof(THING) * (COUNT_ID)
+ COUNT_ID, sizeof(THING)
, ...)
|
- kmalloc
+ kmalloc_array
(
- sizeof(THING) * COUNT_ID
+ COUNT_ID, sizeof(THING)
, ...)
|
- kmalloc
+ kmalloc_array
(
- sizeof(THING) * (COUNT_CONST)
+ COUNT_CONST, sizeof(THING)
, ...)
|
- kmalloc
+ kmalloc_array
(
- sizeof(THING) * COUNT_CONST
+ COUNT_CONST, sizeof(THING)
, ...)
)// 2-factor product, only identifiers.
@@
identifier SIZE, COUNT;
@@- kmalloc
+ kmalloc_array
(
- SIZE * COUNT
+ COUNT, SIZE
, ...)// 3-factor product with 1 sizeof(type) or sizeof(expression), with
// redundant parens removed.
@@
expression THING;
identifier STRIDE, COUNT;
type TYPE;
@@(
kmalloc(
- sizeof(TYPE) * (COUNT) * (STRIDE)
+ array3_size(COUNT, STRIDE, sizeof(TYPE))
, ...)
|
kmalloc(
- sizeof(TYPE) * (COUNT) * STRIDE
+ array3_size(COUNT, STRIDE, sizeof(TYPE))
, ...)
|
kmalloc(
- sizeof(TYPE) * COUNT * (STRIDE)
+ array3_size(COUNT, STRIDE, sizeof(TYPE))
, ...)
|
kmalloc(
- sizeof(TYPE) * COUNT * STRIDE
+ array3_size(COUNT, STRIDE, sizeof(TYPE))
, ...)
|
kmalloc(
- sizeof(THING) * (COUNT) * (STRIDE)
+ array3_size(COUNT, STRIDE, sizeof(THING))
, ...)
|
kmalloc(
- sizeof(THING) * (COUNT) * STRIDE
+ array3_size(COUNT, STRIDE, sizeof(THING))
, ...)
|
kmalloc(
- sizeof(THING) * COUNT * (STRIDE)
+ array3_size(COUNT, STRIDE, sizeof(THING))
, ...)
|
kmalloc(
- sizeof(THING) * COUNT * STRIDE
+ array3_size(COUNT, STRIDE, sizeof(THING))
, ...)
)// 3-factor product with 2 sizeof(variable), with redundant parens removed.
@@
expression THING1, THING2;
identifier COUNT;
type TYPE1, TYPE2;
@@(
kmalloc(
- sizeof(TYPE1) * sizeof(TYPE2) * COUNT
+ array3_size(COUNT, sizeof(TYPE1), sizeof(TYPE2))
, ...)
|
kmalloc(
- sizeof(TYPE1) * sizeof(THING2) * (COUNT)
+ array3_size(COUNT, sizeof(TYPE1), sizeof(TYPE2))
, ...)
|
kmalloc(
- sizeof(THING1) * sizeof(THING2) * COUNT
+ array3_size(COUNT, sizeof(THING1), sizeof(THING2))
, ...)
|
kmalloc(
- sizeof(THING1) * sizeof(THING2) * (COUNT)
+ array3_size(COUNT, sizeof(THING1), sizeof(THING2))
, ...)
|
kmalloc(
- sizeof(TYPE1) * sizeof(THING2) * COUNT
+ array3_size(COUNT, sizeof(TYPE1), sizeof(THING2))
, ...)
|
kmalloc(
- sizeof(TYPE1) * sizeof(THING2) * (COUNT)
+ array3_size(COUNT, sizeof(TYPE1), sizeof(THING2))
, ...)
)// 3-factor product, only identifiers, with redundant parens removed.
@@
identifier STRIDE, SIZE, COUNT;
@@(
kmalloc(
- (COUNT) * STRIDE * SIZE
+ array3_size(COUNT, STRIDE, SIZE)
, ...)
|
kmalloc(
- COUNT * (STRIDE) * SIZE
+ array3_size(COUNT, STRIDE, SIZE)
, ...)
|
kmalloc(
- COUNT * STRIDE * (SIZE)
+ array3_size(COUNT, STRIDE, SIZE)
, ...)
|
kmalloc(
- (COUNT) * (STRIDE) * SIZE
+ array3_size(COUNT, STRIDE, SIZE)
, ...)
|
kmalloc(
- COUNT * (STRIDE) * (SIZE)
+ array3_size(COUNT, STRIDE, SIZE)
, ...)
|
kmalloc(
- (COUNT) * STRIDE * (SIZE)
+ array3_size(COUNT, STRIDE, SIZE)
, ...)
|
kmalloc(
- (COUNT) * (STRIDE) * (SIZE)
+ array3_size(COUNT, STRIDE, SIZE)
, ...)
|
kmalloc(
- COUNT * STRIDE * SIZE
+ array3_size(COUNT, STRIDE, SIZE)
, ...)
)// Any remaining multi-factor products, first at least 3-factor products,
// when they're not all constants...
@@
expression E1, E2, E3;
constant C1, C2, C3;
@@(
kmalloc(C1 * C2 * C3, ...)
|
kmalloc(
- (E1) * E2 * E3
+ array3_size(E1, E2, E3)
, ...)
|
kmalloc(
- (E1) * (E2) * E3
+ array3_size(E1, E2, E3)
, ...)
|
kmalloc(
- (E1) * (E2) * (E3)
+ array3_size(E1, E2, E3)
, ...)
|
kmalloc(
- E1 * E2 * E3
+ array3_size(E1, E2, E3)
, ...)
)// And then all remaining 2 factors products when they're not all constants,
// keeping sizeof() as the second factor argument.
@@
expression THING, E1, E2;
type TYPE;
constant C1, C2, C3;
@@(
kmalloc(sizeof(THING) * C2, ...)
|
kmalloc(sizeof(TYPE) * C2, ...)
|
kmalloc(C1 * C2 * C3, ...)
|
kmalloc(C1 * C2, ...)
|
- kmalloc
+ kmalloc_array
(
- sizeof(TYPE) * (E2)
+ E2, sizeof(TYPE)
, ...)
|
- kmalloc
+ kmalloc_array
(
- sizeof(TYPE) * E2
+ E2, sizeof(TYPE)
, ...)
|
- kmalloc
+ kmalloc_array
(
- sizeof(THING) * (E2)
+ E2, sizeof(THING)
, ...)
|
- kmalloc
+ kmalloc_array
(
- sizeof(THING) * E2
+ E2, sizeof(THING)
, ...)
|
- kmalloc
+ kmalloc_array
(
- (E1) * E2
+ E1, E2
, ...)
|
- kmalloc
+ kmalloc_array
(
- (E1) * (E2)
+ E1, E2
, ...)
|
- kmalloc
+ kmalloc_array
(
- E1 * E2
+ E1, E2
, ...)
)Signed-off-by: Kees Cook
25 Apr, 2018
8 commits
-
To get rid of the variable length arrays on stack in the RS decoder it's
necessary to allocate the decoder buffers per control structure instance.All usage sites have been checked for potential parallel decoder usage and
fixed where necessary. Kees confirmed that the pstore decoding is strictly
single threaded so there should be no surprises.Allocate them in the rs control structure sized depending on the number of
roots for the chosen codec and adapt the decoder code to make use of them.Document the fact that decode operations based on a particular rs control
instance cannot run in parallel and the caller has to ensure that as it's
not possible to provide a proper locking construct which fits all use
cases.Signed-off-by: Thomas Gleixner
Acked-by: Kees Cook
Cc: Boris Brezillon
Cc: Tony Luck
Cc: Segher Boessenkool
Cc: Kernel Hardening
Cc: Richard Weinberger
Cc: Mike Snitzer
Cc: Anton Vorontsov
Cc: Colin Cross
Cc: Andrew Morton
Cc: David Woodhouse
Cc: Alasdair Kergon
Signed-off-by: Kees Cook -
The decoder library uses variable length arrays on stack. To get rid of
them it would be simple to allocate fixed length arrays on stack, but those
might become rather large. The other solution is to allocate the buffers in
the rs control structure, but this cannot be done as long as the structure
can be shared by several users. Sharing is desired because the RS polynom
tables are large and initialization is time consuming.To solve this split the codec information out of the control structure and
have a pointer to a shared codec in it. Instantiate the control structure
for each user, create a new codec if no shareable is avaiable yet. Adjust
all affected usage sites to the new scheme.This allows to add per instance decoder buffers to the control structure
later on.Signed-off-by: Thomas Gleixner
Acked-by: Boris Brezillon
Cc: Tony Luck
Cc: Kees Cook
Cc: Segher Boessenkool
Cc: Kernel Hardening
Cc: Richard Weinberger
Cc: Mike Snitzer
Cc: Anton Vorontsov
Cc: Colin Cross
Cc: Andrew Morton
Cc: David Woodhouse
Cc: Alasdair Kergon
Signed-off-by: Kees Cook -
The four error path labels in rs_init() can be reduced to one by allocating
the struct with kzalloc so the pointers in the struct are NULL and can be
unconditionally handed in to kfree() because they either point to an
allocation or are NULL.Signed-off-by: Thomas Gleixner
Signed-off-by: Kees Cook -
Now that SPDX identifiers are in place, remove the GPL boiler plate
text. Leave the notices which document that Phil Karn granted permission in
place (encode/decode source code). The modified files are code written for
the kernel by me.Signed-off-by: Thomas Gleixner
Reviewed-by: Kate Stewart
Reviewed-by: Greg Kroah-Hartman
Cc: Boris Brezillon
Cc: Tony Luck
Cc: Kees Cook
Cc: Segher Boessenkool
Cc: Kernel Hardening
Cc: Richard Weinberger
Cc: Mike Snitzer
Cc: Anton Vorontsov
Cc: Colin Cross
Cc: Andrew Morton
Cc: David Woodhouse
Cc: Alasdair Kergon
Signed-off-by: Kees Cook -
The Reed-Solomon library is based on code from Phil Karn who granted
permission to import it into the kernel under the GPL V2.See commit 15b5423757a7 ("Shared Reed-Solomon ECC library") in the history
git tree at: git://git.kernel.org/pub/scm/linux/kernel/git/tglx/history.git...
The encoder/decoder code is lifted from the GPL'd userspace RS-library
written by Phil Karn. I modified/wrapped it to provide the different
functions which we need in the MTD/NAND code.
...
Signed-Off-By: Thomas Gleixner
Signed-Off-By: David Woodhouse
"No objections at all. Just keep the authorship notices." -- Phil KarnAdd the proper SPDX identifiers according to
Documentation/process/license-rules.rst.Signed-off-by: Thomas Gleixner
Reviewed-by: Kate Stewart
Reviewed-by: Greg Kroah-Hartman
Cc: Boris Brezillon
Cc: Tony Luck
Cc: Kees Cook
Cc: Segher Boessenkool
Cc: Kernel Hardening
Cc: Richard Weinberger
Cc: Mike Snitzer
Cc: Anton Vorontsov
Cc: Colin Cross
Cc: Andrew Morton
Cc: David Woodhouse
Cc: Alasdair Kergon
Signed-off-by: Kees Cook -
File references and stale CVS ids are really not useful.
Signed-off-by: Thomas Gleixner
Cc: Boris Brezillon
Cc: Tony Luck
Cc: Kees Cook
Cc: Segher Boessenkool
Cc: Kernel Hardening
Cc: Richard Weinberger
Cc: Mike Snitzer
Cc: Anton Vorontsov
Cc: Colin Cross
Cc: Andrew Morton
Cc: David Woodhouse
Cc: Alasdair Kergon
Signed-off-by: Kees Cook -
Instead of mixing the whitespace cleanup into functional changes, mop it up
first.Signed-off-by: Thomas Gleixner
Cc: Boris Brezillon
Cc: Tony Luck
Cc: Kees Cook
Cc: Segher Boessenkool
Cc: Kernel Hardening
Cc: Richard Weinberger
Cc: Mike Snitzer
Cc: Anton Vorontsov
Cc: Colin Cross
Cc: Andrew Morton
Cc: David Woodhouse
Cc: Alasdair Kergon
Signed-off-by: Kees Cook -
The rslib usage in dm/verity_fec is broken because init_rs() can nest in
GFP_NOIO mempool allocations as init_rs() is invoked from the mempool alloc
callback.Provide a variant which takes gfp_t flags as argument.
Signed-off-by: Thomas Gleixner
Cc: Mike Snitzer
Cc: Alasdair Kergon
Cc: Neil Brown
Signed-off-by: Kees Cook
19 Apr, 2008
1 commit
-
reed_solomon doesn't use any of the functionality promised by
asm/semaphore.h.Signed-off-by: Matthew Wilcox
21 Oct, 2007
2 commits
-
Magic numerical values are just bad style. Particularly so when
undocumented.Signed-off-by: Jörn Engel
Signed-off-by: David Woodhouse -
Returning -ERANGE should never happen.
Signed-off-by: Jörn Engel
Signed-off-by: David Woodhouse
02 May, 2007
1 commit
-
For the CAFÉ NAND controller, we need to support non-canonical
representations of the Galois field. Allow the caller to provide its own
function for generating the field, and CAFÉ can use rslib instead of its
own implementation.Signed-off-by: Segher Boessenkool
Signed-off-by: David Woodhouse
04 Oct, 2006
1 commit
-
Many files include the filename at the beginning, serveral used a wrong one.
Signed-off-by: Uwe Zeisberger
Signed-off-by: Adrian Bunk
26 Jun, 2006
1 commit
-
Fix kernel-doc formatting in Reed-Solomon code.
Signed-off-by: Randy Dunlap
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
23 Mar, 2006
1 commit
-
Semaphore to mutex conversion.
The conversion was generated via scripts, and the result was validated
automatically via a script as well.Signed-off-by: Arjan van de Ven
Signed-off-by: Ingo Molnar
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
07 Nov, 2005
1 commit
17 Apr, 2005
1 commit
-
Initial git repository build. I'm not bothering with the full history,
even though we have it. We can create a separate "historical" git
archive of that later if we want to, and in the meantime it's about
3.2GB when imported into git - space that would just make the early
git days unnecessarily complicated, when we don't have a lot of good
infrastructure for it.Let it rip!
