* [RFC v2] Reed-Solomon Code: Update no_eras to the actual number of errors
@ 2020-06-25 7:36 Aiden Leong
2020-06-25 13:06 ` Ferdinand Blomqvist
2020-06-29 22:05 ` kernel test robot
0 siblings, 2 replies; 4+ messages in thread
From: Aiden Leong @ 2020-06-25 7:36 UTC (permalink / raw)
To: Gustavo A. R. Silva, Thomas Gleixner, Ferdinand Blomqvist,
YueHaibing, dm-devel, linux-kernel
Cc: Alasdair Kergon, Mike Snitzer
Corr and eras_pos are updated to actual correction pattern and erasure
positions, but no_eras is not.
When this library is used to recover lost bytes, we normally memset the
lost trunk of bytes to zero as a placeholder. Unfortunately, if the lost
byte is zero, b[i] is zero too. Without correct no_eras, users won't be
able to determine the valid length of corr and eras_pos.
Signed-off-by: Aiden Leong <aiden.leong@aibsd.com>
---
drivers/md/dm-verity-fec.c | 2 +-
include/linux/rslib.h | 4 ++--
lib/reed_solomon/decode_rs.c | 20 ++++++++++++++------
lib/reed_solomon/reed_solomon.c | 4 ++--
lib/reed_solomon/test_rslib.c | 18 ++++++++++++------
5 files changed, 31 insertions(+), 17 deletions(-)
diff --git a/drivers/md/dm-verity-fec.c b/drivers/md/dm-verity-fec.c
index fb41b4f23c48..ae8366a50244 100644
--- a/drivers/md/dm-verity-fec.c
+++ b/drivers/md/dm-verity-fec.c
@@ -50,7 +50,7 @@ static int fec_decode_rs8(struct dm_verity *v, struct dm_verity_fec_io *fio,
for (i = 0; i < v->fec->roots; i++)
par[i] = fec[i];
- return decode_rs8(fio->rs, data, par, v->fec->rsn, NULL, neras,
+ return decode_rs8(fio->rs, data, par, v->fec->rsn, NULL, &neras,
fio->erasures, 0, NULL);
}
diff --git a/include/linux/rslib.h b/include/linux/rslib.h
index 238bb85243d3..80662abc9af7 100644
--- a/include/linux/rslib.h
+++ b/include/linux/rslib.h
@@ -64,7 +64,7 @@ int encode_rs8(struct rs_control *rs, uint8_t *data, int len, uint16_t *par,
#endif
#ifdef CONFIG_REED_SOLOMON_DEC8
int decode_rs8(struct rs_control *rs, uint8_t *data, uint16_t *par, int len,
- uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
+ uint16_t *s, int *no_eras, int *eras_pos, uint16_t invmsk,
uint16_t *corr);
#endif
@@ -75,7 +75,7 @@ int encode_rs16(struct rs_control *rs, uint16_t *data, int len, uint16_t *par,
#endif
#ifdef CONFIG_REED_SOLOMON_DEC16
int decode_rs16(struct rs_control *rs, uint16_t *data, uint16_t *par, int len,
- uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
+ uint16_t *s, int *no_eras, int *eras_pos, uint16_t invmsk,
uint16_t *corr);
#endif
diff --git a/lib/reed_solomon/decode_rs.c b/lib/reed_solomon/decode_rs.c
index 805de84ae83d..44136ea33d16 100644
--- a/lib/reed_solomon/decode_rs.c
+++ b/lib/reed_solomon/decode_rs.c
@@ -24,6 +24,7 @@
int count = 0;
int num_corrected;
uint16_t msk = (uint16_t) rs->nn;
+ int no_eras_local = no_eras ? *no_eras : 0;
/*
* The decoder buffers are in the rs control struct. They are
@@ -106,11 +107,11 @@
memset(&lambda[1], 0, nroots * sizeof(lambda[0]));
lambda[0] = 1;
- if (no_eras > 0) {
+ if (no_eras_local > 0) {
/* Init lambda to be the erasure locator polynomial */
lambda[1] = alpha_to[rs_modnn(rs,
prim * (nn - 1 - (eras_pos[0] + pad)))];
- for (i = 1; i < no_eras; i++) {
+ for (i = 1; i < no_eras_local; i++) {
u = rs_modnn(rs, prim * (nn - 1 - (eras_pos[i] + pad)));
for (j = i + 1; j > 0; j--) {
tmp = index_of[lambda[j - 1]];
@@ -129,8 +130,8 @@
* Begin Berlekamp-Massey algorithm to determine error+erasure
* locator polynomial
*/
- r = no_eras;
- el = no_eras;
+ r = no_eras_local;
+ el = no_eras_local;
while (++r <= nroots) { /* r is the step number */
/* Compute discrepancy at the r-th step in poly-form */
discr_r = 0;
@@ -158,8 +159,8 @@
} else
t[i + 1] = lambda[i + 1];
}
- if (2 * el <= r + no_eras - 1) {
- el = r + no_eras - el;
+ if (2 * el <= r + no_eras_local - 1) {
+ el = r + no_eras_local - el;
/*
* 2 lines below: B(x) <-- inv(discr_r) *
* lambda(x)
@@ -312,14 +313,21 @@
eras_pos[j++] = loc[i] - pad;
}
}
+ if (no_eras)
+ *no_eras = j;
} else if (data && par) {
/* Apply error to data and parity */
+ j = 0;
for (i = 0; i < count; i++) {
if (loc[i] < (nn - nroots))
data[loc[i] - pad] ^= b[i];
else
par[loc[i] - pad - len] ^= b[i];
+ if (b[i])
+ j++;
}
+ if (no_eras)
+ *no_eras = j;
}
return num_corrected;
diff --git a/lib/reed_solomon/reed_solomon.c b/lib/reed_solomon/reed_solomon.c
index bbc01bad3053..b2c811674c98 100644
--- a/lib/reed_solomon/reed_solomon.c
+++ b/lib/reed_solomon/reed_solomon.c
@@ -359,7 +359,7 @@ EXPORT_SYMBOL_GPL(encode_rs8);
* errors. The count includes errors in the parity.
*/
int decode_rs8(struct rs_control *rsc, uint8_t *data, uint16_t *par, int len,
- uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
+ uint16_t *s, int *no_eras, int *eras_pos, uint16_t invmsk,
uint16_t *corr)
{
#include "decode_rs.c"
@@ -410,7 +410,7 @@ EXPORT_SYMBOL_GPL(encode_rs16);
* errors. The count includes errors in the parity.
*/
int decode_rs16(struct rs_control *rsc, uint16_t *data, uint16_t *par, int len,
- uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
+ uint16_t *s, int *no_eras, int *eras_pos, uint16_t invmsk,
uint16_t *corr)
{
#include "decode_rs.c"
diff --git a/lib/reed_solomon/test_rslib.c b/lib/reed_solomon/test_rslib.c
index 4eb29f365ece..b30a4aea8796 100644
--- a/lib/reed_solomon/test_rslib.c
+++ b/lib/reed_solomon/test_rslib.c
@@ -258,7 +258,7 @@ static void compute_syndrome(struct rs_control *rsc, uint16_t *data,
/* Test up to error correction capacity */
static void test_uc(struct rs_control *rs, int len, int errs,
- int eras, int trials, struct estat *stat,
+ int *eras, int trials, struct estat *stat,
struct wspace *ws, int method)
{
int dlen = len - rs->codec->nroots;
@@ -327,8 +327,11 @@ static int ex_rs_helper(struct rs_control *rs, struct wspace *ws,
pr_info(" %s\n", desc[method]);
for (errs = 0; errs <= nroots / 2; errs++)
- for (eras = 0; eras <= nroots - 2 * errs; eras++)
- test_uc(rs, len, errs, eras, trials, &stat, ws, method);
+ for (eras = 0; eras <= nroots - 2 * errs; eras++) {
+ int no_eras = ers;
+
+ test_uc(rs, len, errs, &no_eras, trials, &stat, ws, method);
+ }
if (v >= V_CSUMMARY) {
pr_info(" Decodes wrong: %d / %d\n",
@@ -364,7 +367,7 @@ static int exercise_rs(struct rs_control *rs, struct wspace *ws,
/* Tests for correct behaviour beyond error correction capacity */
static void test_bc(struct rs_control *rs, int len, int errs,
- int eras, int trials, struct bcstat *stat,
+ int *eras, int trials, struct bcstat *stat,
struct wspace *ws)
{
int nroots = rs->codec->nroots;
@@ -420,8 +423,11 @@ static int exercise_rs_bc(struct rs_control *rs, struct wspace *ws,
eras = 0;
cutoff = nroots <= len - errs ? nroots : len - errs;
- for (; eras <= cutoff; eras++)
- test_bc(rs, len, errs, eras, trials, &stat, ws);
+ for (; eras <= cutoff; eras++) {
+ int no_eras = eras;
+
+ test_bc(rs, len, errs, &no_eras, trials, &stat, ws);
+ }
}
if (v >= V_CSUMMARY) {
--
2.25.1
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [RFC v2] Reed-Solomon Code: Update no_eras to the actual number of errors
2020-06-25 7:36 [RFC v2] Reed-Solomon Code: Update no_eras to the actual number of errors Aiden Leong
@ 2020-06-25 13:06 ` Ferdinand Blomqvist
2020-06-25 13:20 ` Aiden Leong
2020-06-29 22:05 ` kernel test robot
1 sibling, 1 reply; 4+ messages in thread
From: Ferdinand Blomqvist @ 2020-06-25 13:06 UTC (permalink / raw)
To: Aiden Leong
Cc: Gustavo A. R. Silva, Thomas Gleixner, YueHaibing, dm-devel,
linux-kernel, Alasdair Kergon, Mike Snitzer
Hi!
On 2020-06-25 00:36:01, Aiden Leong wrote:
>Corr and eras_pos are updated to actual correction pattern and erasure
>positions, but no_eras is not.
>
>When this library is used to recover lost bytes, we normally memset the
>lost trunk of bytes to zero as a placeholder. Unfortunately, if the lost
>byte is zero, b[i] is zero too. Without correct no_eras, users won't be
>able to determine the valid length of corr and eras_pos.
>
>Signed-off-by: Aiden Leong <aiden.leong@aibsd.com>
I'm not sure I understand what you try to do. decode_rs* already returns
the number of errors correted (or something negative upon failure). So
your last statment is false. The lengt of corr and eras_pos is returned
by the function. So this change is unnecessary. More comments inline.
>
>diff --git a/lib/reed_solomon/decode_rs.c b/lib/reed_solomon/decode_rs.c
>index 805de84ae83d..44136ea33d16 100644
>--- a/lib/reed_solomon/decode_rs.c
>+++ b/lib/reed_solomon/decode_rs.c
>@@ -24,6 +24,7 @@
> int count = 0;
> int num_corrected;
> uint16_t msk = (uint16_t) rs->nn;
>+ int no_eras_local = no_eras ? *no_eras : 0;
>
> /*
> * The decoder buffers are in the rs control struct. They are
>@@ -106,11 +107,11 @@
> memset(&lambda[1], 0, nroots * sizeof(lambda[0]));
> lambda[0] = 1;
>
>- if (no_eras > 0) {
>+ if (no_eras_local > 0) {
> /* Init lambda to be the erasure locator polynomial */
> lambda[1] = alpha_to[rs_modnn(rs,
> prim * (nn - 1 - (eras_pos[0] + pad)))];
>- for (i = 1; i < no_eras; i++) {
>+ for (i = 1; i < no_eras_local; i++) {
> u = rs_modnn(rs, prim * (nn - 1 - (eras_pos[i] + pad)));
> for (j = i + 1; j > 0; j--) {
> tmp = index_of[lambda[j - 1]];
>@@ -129,8 +130,8 @@
> * Begin Berlekamp-Massey algorithm to determine error+erasure
> * locator polynomial
> */
>- r = no_eras;
>- el = no_eras;
>+ r = no_eras_local;
>+ el = no_eras_local;
> while (++r <= nroots) { /* r is the step number */
> /* Compute discrepancy at the r-th step in poly-form */
> discr_r = 0;
>@@ -158,8 +159,8 @@
> } else
> t[i + 1] = lambda[i + 1];
> }
>- if (2 * el <= r + no_eras - 1) {
>- el = r + no_eras - el;
>+ if (2 * el <= r + no_eras_local - 1) {
>+ el = r + no_eras_local - el;
> /*
> * 2 lines below: B(x) <-- inv(discr_r) *
> * lambda(x)
>@@ -312,14 +313,21 @@
> eras_pos[j++] = loc[i] - pad;
> }
> }
>+ if (no_eras)
>+ *no_eras = j;
At this point j will be equal to num_corrected. So why return this
information in no_eras, when it is already returned by the function?
> } else if (data && par) {
> /* Apply error to data and parity */
>+ j = 0;
> for (i = 0; i < count; i++) {
> if (loc[i] < (nn - nroots))
> data[loc[i] - pad] ^= b[i];
> else
> par[loc[i] - pad - len] ^= b[i];
>+ if (b[i])
>+ j++;
> }
>+ if (no_eras)
>+ *no_eras = j;
Same as above.
>2.25.1
>
Best,
Ferdinand
--
Ferdinand Blomqvist
ferdinand.blomqvist[at]gmail.com
GPG key: 9EFB 7A2C 0432 4EC5 32BA FA61 CFE9 4164 93E8 B9E4
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [RFC v2] Reed-Solomon Code: Update no_eras to the actual number of errors
2020-06-25 13:06 ` Ferdinand Blomqvist
@ 2020-06-25 13:20 ` Aiden Leong
0 siblings, 0 replies; 4+ messages in thread
From: Aiden Leong @ 2020-06-25 13:20 UTC (permalink / raw)
To: Ferdinand Blomqvist
Cc: Gustavo A. R. Silva, Thomas Gleixner, YueHaibing, dm-devel,
linux-kernel, Alasdair Kergon, Mike Snitzer
Hi,
You are right. I forgot the return value is number of errors rather than
status code.
Sorry to bother you.
On 6/25/20 6:06 AM, Ferdinand Blomqvist wrote:
> Hi!
>
> On 2020-06-25 00:36:01, Aiden Leong wrote:
>> Corr and eras_pos are updated to actual correction pattern and erasure
>> positions, but no_eras is not.
>>
>> When this library is used to recover lost bytes, we normally memset the
>> lost trunk of bytes to zero as a placeholder. Unfortunately, if the lost
>> byte is zero, b[i] is zero too. Without correct no_eras, users won't be
>> able to determine the valid length of corr and eras_pos.
>>
>> Signed-off-by: Aiden Leong <aiden.leong@aibsd.com>
>
> I'm not sure I understand what you try to do. decode_rs* already returns
> the number of errors correted (or something negative upon failure). So
> your last statment is false. The lengt of corr and eras_pos is returned
> by the function. So this change is unnecessary. More comments inline.
>
>>
>> diff --git a/lib/reed_solomon/decode_rs.c b/lib/reed_solomon/decode_rs.c
>> index 805de84ae83d..44136ea33d16 100644
>> --- a/lib/reed_solomon/decode_rs.c
>> +++ b/lib/reed_solomon/decode_rs.c
>> @@ -24,6 +24,7 @@
>> int count = 0;
>> int num_corrected;
>> uint16_t msk = (uint16_t) rs->nn;
>> + int no_eras_local = no_eras ? *no_eras : 0;
>>
>> /*
>> * The decoder buffers are in the rs control struct. They are
>> @@ -106,11 +107,11 @@
>> memset(&lambda[1], 0, nroots * sizeof(lambda[0]));
>> lambda[0] = 1;
>>
>> - if (no_eras > 0) {
>> + if (no_eras_local > 0) {
>> /* Init lambda to be the erasure locator polynomial */
>> lambda[1] = alpha_to[rs_modnn(rs,
>> prim * (nn - 1 - (eras_pos[0] + pad)))];
>> - for (i = 1; i < no_eras; i++) {
>> + for (i = 1; i < no_eras_local; i++) {
>> u = rs_modnn(rs, prim * (nn - 1 - (eras_pos[i] + pad)));
>> for (j = i + 1; j > 0; j--) {
>> tmp = index_of[lambda[j - 1]];
>> @@ -129,8 +130,8 @@
>> * Begin Berlekamp-Massey algorithm to determine error+erasure
>> * locator polynomial
>> */
>> - r = no_eras;
>> - el = no_eras;
>> + r = no_eras_local;
>> + el = no_eras_local;
>> while (++r <= nroots) { /* r is the step number */
>> /* Compute discrepancy at the r-th step in poly-form */
>> discr_r = 0;
>> @@ -158,8 +159,8 @@
>> } else
>> t[i + 1] = lambda[i + 1];
>> }
>> - if (2 * el <= r + no_eras - 1) {
>> - el = r + no_eras - el;
>> + if (2 * el <= r + no_eras_local - 1) {
>> + el = r + no_eras_local - el;
>> /*
>> * 2 lines below: B(x) <-- inv(discr_r) *
>> * lambda(x)
>> @@ -312,14 +313,21 @@
>> eras_pos[j++] = loc[i] - pad;
>> }
>> }
>> + if (no_eras)
>> + *no_eras = j;
> At this point j will be equal to num_corrected. So why return this
> information in no_eras, when it is already returned by the function?
>
>> } else if (data && par) {
>> /* Apply error to data and parity */
>> + j = 0;
>> for (i = 0; i < count; i++) {
>> if (loc[i] < (nn - nroots))
>> data[loc[i] - pad] ^= b[i];
>> else
>> par[loc[i] - pad - len] ^= b[i];
>> + if (b[i])
>> + j++;
>> }
>> + if (no_eras)
>> + *no_eras = j;
>
> Same as above.
>
>> 2.25.1
>>
>
> Best,
> Ferdinand
>
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [RFC v2] Reed-Solomon Code: Update no_eras to the actual number of errors
2020-06-25 7:36 [RFC v2] Reed-Solomon Code: Update no_eras to the actual number of errors Aiden Leong
2020-06-25 13:06 ` Ferdinand Blomqvist
@ 2020-06-29 22:05 ` kernel test robot
1 sibling, 0 replies; 4+ messages in thread
From: kernel test robot @ 2020-06-29 22:05 UTC (permalink / raw)
To: kbuild-all
[-- Attachment #1: Type: text/plain, Size: 4287 bytes --]
Hi Aiden,
[FYI, it's a private test report for your RFC patch.]
[auto build test ERROR on dm/for-next]
[also build test ERROR on linux/master linus/master v5.8-rc3 next-20200629]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use as documented in
https://git-scm.com/docs/git-format-patch]
url: https://github.com/0day-ci/linux/commits/Aiden-Leong/Reed-Solomon-Code-Update-no_eras-to-the-actual-number-of-errors/20200625-153849
base: https://git.kernel.org/pub/scm/linux/kernel/git/device-mapper/linux-dm.git for-next
config: sh-allyesconfig (attached as .config)
compiler: sh4-linux-gcc (GCC) 9.3.0
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-9.3.0 make.cross ARCH=sh
If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@intel.com>
All errors (new ones prefixed by >>):
lib/reed_solomon/test_rslib.c: In function 'test_uc':
lib/reed_solomon/test_rslib.c:275:41: warning: passing argument 5 of 'get_rcw_we' makes integer from pointer without a cast [-Wint-conversion]
275 | nerrs = get_rcw_we(rs, ws, len, errs, eras);
| ^~~~
| |
| int *
lib/reed_solomon/test_rslib.c:152:27: note: expected 'int' but argument is of type 'int *'
152 | int len, int errs, int eras)
| ~~~~^~~~
lib/reed_solomon/test_rslib.c: In function 'ex_rs_helper':
>> lib/reed_solomon/test_rslib.c:331:18: error: 'ers' undeclared (first use in this function); did you mean 'eras'?
331 | int no_eras = ers;
| ^~~
| eras
lib/reed_solomon/test_rslib.c:331:18: note: each undeclared identifier is reported only once for each function it appears in
lib/reed_solomon/test_rslib.c: In function 'test_bc':
lib/reed_solomon/test_rslib.c:381:33: warning: passing argument 5 of 'get_rcw_we' makes integer from pointer without a cast [-Wint-conversion]
381 | get_rcw_we(rs, ws, len, errs, eras);
| ^~~~
| |
| int *
lib/reed_solomon/test_rslib.c:152:27: note: expected 'int' but argument is of type 'int *'
152 | int len, int errs, int eras)
| ~~~~^~~~
vim +331 lib/reed_solomon/test_rslib.c
312
313 static int ex_rs_helper(struct rs_control *rs, struct wspace *ws,
314 int len, int trials, int method)
315 {
316 static const char * const desc[] = {
317 "Testing correction buffer interface...",
318 "Testing with caller provided syndrome...",
319 "Testing in-place interface..."
320 };
321
322 struct estat stat = {0, 0, 0, 0};
323 int nroots = rs->codec->nroots;
324 int errs, eras, retval;
325
326 if (v >= V_PROGRESS)
327 pr_info(" %s\n", desc[method]);
328
329 for (errs = 0; errs <= nroots / 2; errs++)
330 for (eras = 0; eras <= nroots - 2 * errs; eras++) {
> 331 int no_eras = ers;
332
333 test_uc(rs, len, errs, &no_eras, trials, &stat, ws, method);
334 }
335
336 if (v >= V_CSUMMARY) {
337 pr_info(" Decodes wrong: %d / %d\n",
338 stat.dwrong, stat.nwords);
339 pr_info(" Wrong return value: %d / %d\n",
340 stat.irv, stat.nwords);
341 if (method != IN_PLACE)
342 pr_info(" Wrong error position: %d\n", stat.wepos);
343 }
344
345 retval = stat.dwrong + stat.wepos + stat.irv;
346 if (retval && v >= V_PROGRESS)
347 pr_warn(" FAIL: %d decoding failures!\n", retval);
348
349 return retval;
350 }
351
---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org
[-- Attachment #2: config.gz --]
[-- Type: application/gzip, Size: 56053 bytes --]
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2020-06-29 22:05 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2020-06-25 7:36 [RFC v2] Reed-Solomon Code: Update no_eras to the actual number of errors Aiden Leong
2020-06-25 13:06 ` Ferdinand Blomqvist
2020-06-25 13:20 ` Aiden Leong
2020-06-29 22:05 ` kernel test robot
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.