From a5f7a5bb3b7f28ba7e4fa246775b29a0e5537255 Mon Sep 17 00:00:00 2001 From: Jinke Han Date: Tue, 8 Sep 2026 15:37:42 +0800 Subject: x86/kprobes: Fix crash when probing CS CALL instructions When using eBPF to probe CS CALL instructions within a function, a crash can be triggered. The eBPF tool probes offset 257 of the __hrtimer_run_queues() function: <__hrtimer_run_queues+249>: nopl 0x0(%rax,%rax,1) <__hrtimer_run_queues+254>: mov %r14,%rdi <__hrtimer_run_queues+257>: cs call <__x86_indirect_thunk_r12> <__hrtimer_run_queues+263>: mov %eax,%r12d <__hrtimer_run_queues+266>: xchg %ax,%ax <__hrtimer_run_queues+268>: mov %r13,%rdi Which triggers this crash: BUG: unable to handle page fault for address: 00000000000f41c9 #PF: supervisor write access in kernel mode #PF: error_code(0x0002) - not-present page PGD 0 P4D 0 Oops: 0002 [#1] SMP NOPTI CPU: 1 PID: 0 Comm: swapper/1 Kdump: loaded Tainted: P RIP: 0010:__hrtimer_run_queues+0x106/0x230 Note that __hrtimer_run_queues+0x106 is __hrtimer_run_queues+262, which is at the 6th byte of the above CS CALL instruction. Since the CS CALL instruction occupies 6 bytes, the exception occurred in the middle of that call instruction. The root cause is that when using eBPF tools to probe in the middle of a function, a kprobe with INT3 is used as the underlying implementation. During single-step emulation of the original CALL instruction, int3_emulate_call() assumes that the probed CALL instruction is 5 bytes long. However, the actual CS-prefixed CALL instruction occupies 6 bytes, so it constructs an incorrect exception return address. When the CPU returns from the kprobe handler, the next instruction to be executed is at the address of the last byte of that CS CALL instruction. Coincidentally, starting from that address, the CPU fetches and decodes a completely different instruction, which ultimately triggers a kernel crash. Fix the issue by using the actual instruction length obtained from the instruction decoder when constructing the exception return address, rather than relying on the hardcoded CALL_INSN_SIZE macro. [ mingo: Refined the changelog ] Fixes: 6256e668b7af ("x86/kprobes: Use int3 instead of debug trap for single-step") Suggested-by: Masami Hiramatsu (Google) Signed-off-by: Jinke Han Signed-off-by: Ingo Molnar Reviewed-by: Masami Hiramatsu (Google) Acked-by: Yafang Shao Acked-by: Borislav Petkov Cc: Peter Zijlstra Link: https://patch.msgid.link/20260908073742.GA10517@didi-ThinkCentre-M920t-N000 --- lib/reed_solomon/Makefile | 7 + lib/reed_solomon/decode_rs.c | 326 +++++++++++++++++++++++++ lib/reed_solomon/encode_rs.c | 47 ++++ lib/reed_solomon/reed_solomon.c | 424 ++++++++++++++++++++++++++++++++ lib/reed_solomon/test_rslib.c | 518 ++++++++++++++++++++++++++++++++++++++++ 5 files changed, 1322 insertions(+) create mode 100644 lib/reed_solomon/Makefile create mode 100644 lib/reed_solomon/decode_rs.c create mode 100644 lib/reed_solomon/encode_rs.c create mode 100644 lib/reed_solomon/reed_solomon.c create mode 100644 lib/reed_solomon/test_rslib.c (limited to 'lib/reed_solomon') diff --git a/lib/reed_solomon/Makefile b/lib/reed_solomon/Makefile new file mode 100644 index 000000000..5d4fa68f2 --- /dev/null +++ b/lib/reed_solomon/Makefile @@ -0,0 +1,7 @@ +# SPDX-License-Identifier: GPL-2.0-only +# +# This is a modified version of reed solomon lib, +# + +obj-$(CONFIG_REED_SOLOMON) += reed_solomon.o +obj-$(CONFIG_REED_SOLOMON_TEST) += test_rslib.o diff --git a/lib/reed_solomon/decode_rs.c b/lib/reed_solomon/decode_rs.c new file mode 100644 index 000000000..ef86ee2ae --- /dev/null +++ b/lib/reed_solomon/decode_rs.c @@ -0,0 +1,326 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Generic Reed Solomon encoder / decoder library + * + * Copyright 2002, Phil Karn, KA9Q + * May be used under the terms of the GNU General Public License (GPL) + * + * Adaption to the kernel by Thomas Gleixner (tglx@kernel.org) + * + * Generic data width independent code which is included by the wrappers. + */ +{ + struct rs_codec *rs = rsc->codec; + int deg_lambda, el, deg_omega; + int i, j, r, k, pad; + int nn = rs->nn; + int nroots = rs->nroots; + int fcr = rs->fcr; + int prim = rs->prim; + int iprim = rs->iprim; + uint16_t *alpha_to = rs->alpha_to; + uint16_t *index_of = rs->index_of; + uint16_t u, q, tmp, num1, num2, den, discr_r, syn_error; + int count = 0; + int num_corrected; + uint16_t msk = (uint16_t) rs->nn; + + /* + * The decoder buffers are in the rs control struct. They are + * arrays sized [nroots + 1] + */ + uint16_t *lambda = rsc->buffers + RS_DECODE_LAMBDA * (nroots + 1); + uint16_t *syn = rsc->buffers + RS_DECODE_SYN * (nroots + 1); + uint16_t *b = rsc->buffers + RS_DECODE_B * (nroots + 1); + uint16_t *t = rsc->buffers + RS_DECODE_T * (nroots + 1); + uint16_t *omega = rsc->buffers + RS_DECODE_OMEGA * (nroots + 1); + uint16_t *root = rsc->buffers + RS_DECODE_ROOT * (nroots + 1); + uint16_t *reg = rsc->buffers + RS_DECODE_REG * (nroots + 1); + uint16_t *loc = rsc->buffers + RS_DECODE_LOC * (nroots + 1); + + /* Check length parameter for validity */ + pad = nn - nroots - len; + BUG_ON(pad < 0 || pad >= nn - nroots); + + /* Does the caller provide the syndrome ? */ + if (s != NULL) { + for (i = 0; i < nroots; i++) { + /* The syndrome is in index form, + * so nn represents zero + */ + if (s[i] != nn) + goto decode; + } + + /* syndrome is zero, no errors to correct */ + return 0; + } + + /* form the syndromes; i.e., evaluate data(x) at roots of + * g(x) */ + for (i = 0; i < nroots; i++) + syn[i] = (((uint16_t) data[0]) ^ invmsk) & msk; + + for (j = 1; j < len; j++) { + for (i = 0; i < nroots; i++) { + if (syn[i] == 0) { + syn[i] = (((uint16_t) data[j]) ^ + invmsk) & msk; + } else { + syn[i] = ((((uint16_t) data[j]) ^ + invmsk) & msk) ^ + alpha_to[rs_modnn(rs, index_of[syn[i]] + + (fcr + i) * prim)]; + } + } + } + + for (j = 0; j < nroots; j++) { + for (i = 0; i < nroots; i++) { + if (syn[i] == 0) { + syn[i] = ((uint16_t) par[j]) & msk; + } else { + syn[i] = (((uint16_t) par[j]) & msk) ^ + alpha_to[rs_modnn(rs, index_of[syn[i]] + + (fcr+i)*prim)]; + } + } + } + s = syn; + + /* Convert syndromes to index form, checking for nonzero condition */ + syn_error = 0; + for (i = 0; i < nroots; i++) { + syn_error |= s[i]; + s[i] = index_of[s[i]]; + } + + if (!syn_error) { + /* if syndrome is zero, data[] is a codeword and there are no + * errors to correct. So return data[] unmodified + */ + return 0; + } + + decode: + memset(&lambda[1], 0, nroots * sizeof(lambda[0])); + lambda[0] = 1; + + if (no_eras > 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++) { + u = rs_modnn(rs, prim * (nn - 1 - (eras_pos[i] + pad))); + for (j = i + 1; j > 0; j--) { + tmp = index_of[lambda[j - 1]]; + if (tmp != nn) { + lambda[j] ^= + alpha_to[rs_modnn(rs, u + tmp)]; + } + } + } + } + + for (i = 0; i < nroots + 1; i++) + b[i] = index_of[lambda[i]]; + + /* + * Begin Berlekamp-Massey algorithm to determine error+erasure + * locator polynomial + */ + r = no_eras; + el = no_eras; + while (++r <= nroots) { /* r is the step number */ + /* Compute discrepancy at the r-th step in poly-form */ + discr_r = 0; + for (i = 0; i < r; i++) { + if ((lambda[i] != 0) && (s[r - i - 1] != nn)) { + discr_r ^= + alpha_to[rs_modnn(rs, + index_of[lambda[i]] + + s[r - i - 1])]; + } + } + discr_r = index_of[discr_r]; /* Index form */ + if (discr_r == nn) { + /* 2 lines below: B(x) <-- x*B(x) */ + memmove (&b[1], b, nroots * sizeof (b[0])); + b[0] = nn; + } else { + /* 7 lines below: T(x) <-- lambda(x)-discr_r*x*b(x) */ + t[0] = lambda[0]; + for (i = 0; i < nroots; i++) { + if (b[i] != nn) { + t[i + 1] = lambda[i + 1] ^ + alpha_to[rs_modnn(rs, discr_r + + b[i])]; + } else + t[i + 1] = lambda[i + 1]; + } + if (2 * el <= r + no_eras - 1) { + el = r + no_eras - el; + /* + * 2 lines below: B(x) <-- inv(discr_r) * + * lambda(x) + */ + for (i = 0; i <= nroots; i++) { + b[i] = (lambda[i] == 0) ? nn : + rs_modnn(rs, index_of[lambda[i]] + - discr_r + nn); + } + } else { + /* 2 lines below: B(x) <-- x*B(x) */ + memmove(&b[1], b, nroots * sizeof(b[0])); + b[0] = nn; + } + memcpy(lambda, t, (nroots + 1) * sizeof(t[0])); + } + } + + /* Convert lambda to index form and compute deg(lambda(x)) */ + deg_lambda = 0; + for (i = 0; i < nroots + 1; i++) { + lambda[i] = index_of[lambda[i]]; + if (lambda[i] != nn) + deg_lambda = i; + } + + if (deg_lambda == 0) { + /* + * deg(lambda) is zero even though the syndrome is non-zero + * => uncorrectable error detected + */ + return -EBADMSG; + } + + /* Find roots of error+erasure locator polynomial by Chien search */ + memcpy(®[1], &lambda[1], nroots * sizeof(reg[0])); + count = 0; /* Number of roots of lambda(x) */ + for (i = 1, k = iprim - 1; i <= nn; i++, k = rs_modnn(rs, k + iprim)) { + q = 1; /* lambda[0] is always 0 */ + for (j = deg_lambda; j > 0; j--) { + if (reg[j] != nn) { + reg[j] = rs_modnn(rs, reg[j] + j); + q ^= alpha_to[reg[j]]; + } + } + if (q != 0) + continue; /* Not a root */ + + if (k < pad) { + /* Impossible error location. Uncorrectable error. */ + return -EBADMSG; + } + + /* store root (index-form) and error location number */ + root[count] = i; + loc[count] = k; + /* If we've already found max possible roots, + * abort the search to save time + */ + if (++count == deg_lambda) + break; + } + if (deg_lambda != count) { + /* + * deg(lambda) unequal to number of roots => uncorrectable + * error detected + */ + return -EBADMSG; + } + /* + * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo + * x**nroots). in index form. Also find deg(omega). + */ + deg_omega = deg_lambda - 1; + for (i = 0; i <= deg_omega; i++) { + tmp = 0; + for (j = i; j >= 0; j--) { + if ((s[i - j] != nn) && (lambda[j] != nn)) + tmp ^= + alpha_to[rs_modnn(rs, s[i - j] + lambda[j])]; + } + omega[i] = index_of[tmp]; + } + + /* + * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 = + * inv(X(l))**(fcr-1) and den = lambda_pr(inv(X(l))) all in poly-form + * Note: we reuse the buffer for b to store the correction pattern + */ + num_corrected = 0; + for (j = count - 1; j >= 0; j--) { + num1 = 0; + for (i = deg_omega; i >= 0; i--) { + if (omega[i] != nn) + num1 ^= alpha_to[rs_modnn(rs, omega[i] + + i * root[j])]; + } + + if (num1 == 0) { + /* Nothing to correct at this position */ + b[j] = 0; + continue; + } + + num2 = alpha_to[rs_modnn(rs, root[j] * (fcr - 1) + nn)]; + den = 0; + + /* lambda[i+1] for i even is the formal derivative + * lambda_pr of lambda[i] */ + for (i = min(deg_lambda, nroots - 1) & ~1; i >= 0; i -= 2) { + if (lambda[i + 1] != nn) { + den ^= alpha_to[rs_modnn(rs, lambda[i + 1] + + i * root[j])]; + } + } + + b[j] = alpha_to[rs_modnn(rs, index_of[num1] + + index_of[num2] + + nn - index_of[den])]; + num_corrected++; + } + + /* + * We compute the syndrome of the 'error' and check that it matches + * the syndrome of the received word + */ + for (i = 0; i < nroots; i++) { + tmp = 0; + for (j = 0; j < count; j++) { + if (b[j] == 0) + continue; + + k = (fcr + i) * prim * (nn-loc[j]-1); + tmp ^= alpha_to[rs_modnn(rs, index_of[b[j]] + k)]; + } + + if (tmp != alpha_to[s[i]]) + return -EBADMSG; + } + + /* + * Store the error correction pattern, if a + * correction buffer is available + */ + if (corr && eras_pos) { + j = 0; + for (i = 0; i < count; i++) { + if (b[i]) { + corr[j] = b[i]; + eras_pos[j++] = loc[i] - pad; + } + } + } else if (data && par) { + /* Apply error to data and parity */ + 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]; + } + } + + return num_corrected; +} diff --git a/lib/reed_solomon/encode_rs.c b/lib/reed_solomon/encode_rs.c new file mode 100644 index 000000000..1d9e51dcc --- /dev/null +++ b/lib/reed_solomon/encode_rs.c @@ -0,0 +1,47 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Generic Reed Solomon encoder / decoder library + * + * Copyright 2002, Phil Karn, KA9Q + * May be used under the terms of the GNU General Public License (GPL) + * + * Adaption to the kernel by Thomas Gleixner (tglx@kernel.org) + * + * Generic data width independent code which is included by the wrappers. + */ +{ + struct rs_codec *rs = rsc->codec; + int i, j, pad; + int nn = rs->nn; + int nroots = rs->nroots; + uint16_t *alpha_to = rs->alpha_to; + uint16_t *index_of = rs->index_of; + uint16_t *genpoly = rs->genpoly; + uint16_t fb; + uint16_t msk = (uint16_t) rs->nn; + + /* Check length parameter for validity */ + pad = nn - nroots - len; + if (pad < 0 || pad >= nn) + return -ERANGE; + + for (i = 0; i < len; i++) { + fb = index_of[((((uint16_t) data[i])^invmsk) & msk) ^ par[0]]; + /* feedback term is non-zero */ + if (fb != nn) { + for (j = 1; j < nroots; j++) { + par[j] ^= alpha_to[rs_modnn(rs, fb + + genpoly[nroots - j])]; + } + } + /* Shift */ + memmove(&par[0], &par[1], sizeof(uint16_t) * (nroots - 1)); + if (fb != nn) { + par[nroots - 1] = alpha_to[rs_modnn(rs, + fb + genpoly[0])]; + } else { + par[nroots - 1] = 0; + } + } + return 0; +} diff --git a/lib/reed_solomon/reed_solomon.c b/lib/reed_solomon/reed_solomon.c new file mode 100644 index 000000000..864484c01 --- /dev/null +++ b/lib/reed_solomon/reed_solomon.c @@ -0,0 +1,424 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Generic Reed Solomon encoder / decoder library + * + * Copyright (C) 2004 Thomas Gleixner (tglx@kernel.org) + * + * Reed Solomon code lifted from reed solomon library written by Phil Karn + * Copyright 2002 Phil Karn, KA9Q + * + * Description: + * + * The generic Reed Solomon library provides runtime configurable + * encoding / decoding of RS codes. + * + * Each user must call init_rs to get a pointer to a rs_control structure + * for the given rs parameters. The control struct is unique per instance. + * It points to a codec which can be shared by multiple control structures. + * If a codec is newly allocated then the polynomial arrays for fast + * encoding / decoding are built. This can take some time so make sure not + * to call this function from a time critical path. Usually a module / + * driver should initialize the necessary rs_control structure on module / + * driver init and release it on exit. + * + * The encoding puts the calculated syndrome into a given syndrome buffer. + * + * The decoding is a two step process. The first step calculates the + * syndrome over the received (data + syndrome) and calls the second stage, + * which does the decoding / error correction itself. Many hw encoders + * provide a syndrome calculation over the received data + syndrome and can + * call the second stage directly. + */ +#include +#include +#include +#include +#include +#include +#include + +enum { + RS_DECODE_LAMBDA, + RS_DECODE_SYN, + RS_DECODE_B, + RS_DECODE_T, + RS_DECODE_OMEGA, + RS_DECODE_ROOT, + RS_DECODE_REG, + RS_DECODE_LOC, + RS_DECODE_NUM_BUFFERS +}; + +/* This list holds all currently allocated rs codec structures */ +static LIST_HEAD(codec_list); +/* Protection for the list */ +static DEFINE_MUTEX(rslistlock); + +/** + * codec_init - Initialize a Reed-Solomon codec + * @symsize: symbol size, bits (1-8) + * @gfpoly: Field generator polynomial coefficients + * @gffunc: Field generator function + * @fcr: first root of RS code generator polynomial, index form + * @prim: primitive element to generate polynomial roots + * @nroots: RS code generator polynomial degree (number of roots) + * @gfp: GFP_ flags for allocations + * + * Allocate a codec structure and the polynom arrays for faster + * en/decoding. Fill the arrays according to the given parameters. + */ +static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int), + int fcr, int prim, int nroots, gfp_t gfp) +{ + int i, j, sr, root, iprim; + struct rs_codec *rs; + + rs = kzalloc_obj(*rs, gfp); + if (!rs) + return NULL; + + INIT_LIST_HEAD(&rs->list); + + rs->mm = symsize; + rs->nn = (1 << symsize) - 1; + rs->fcr = fcr; + rs->prim = prim; + rs->nroots = nroots; + rs->gfpoly = gfpoly; + rs->gffunc = gffunc; + + /* Allocate the arrays */ + rs->alpha_to = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp); + if (rs->alpha_to == NULL) + goto err; + + rs->index_of = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp); + if (rs->index_of == NULL) + goto err; + + rs->genpoly = kmalloc_array(rs->nroots + 1, sizeof(uint16_t), gfp); + if(rs->genpoly == NULL) + goto err; + + /* Generate Galois field lookup tables */ + rs->index_of[0] = rs->nn; /* log(zero) = -inf */ + rs->alpha_to[rs->nn] = 0; /* alpha**-inf = 0 */ + if (gfpoly) { + sr = 1; + for (i = 0; i < rs->nn; i++) { + rs->index_of[sr] = i; + rs->alpha_to[i] = sr; + sr <<= 1; + if (sr & (1 << symsize)) + sr ^= gfpoly; + sr &= rs->nn; + } + } else { + sr = gffunc(0); + for (i = 0; i < rs->nn; i++) { + rs->index_of[sr] = i; + rs->alpha_to[i] = sr; + sr = gffunc(sr); + } + } + /* If it's not primitive, exit */ + if(sr != rs->alpha_to[0]) + goto err; + + /* Find prim-th root of 1, used in decoding */ + for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn); + /* prim-th root of 1, index form */ + rs->iprim = iprim / prim; + + /* Form RS code generator polynomial from its roots */ + rs->genpoly[0] = 1; + for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) { + rs->genpoly[i + 1] = 1; + /* Multiply rs->genpoly[] by @**(root + x) */ + for (j = i; j > 0; j--) { + if (rs->genpoly[j] != 0) { + rs->genpoly[j] = rs->genpoly[j -1] ^ + rs->alpha_to[rs_modnn(rs, + rs->index_of[rs->genpoly[j]] + root)]; + } else + rs->genpoly[j] = rs->genpoly[j - 1]; + } + /* rs->genpoly[0] can never be zero */ + rs->genpoly[0] = + rs->alpha_to[rs_modnn(rs, + rs->index_of[rs->genpoly[0]] + root)]; + } + /* convert rs->genpoly[] to index form for quicker encoding */ + for (i = 0; i <= nroots; i++) + rs->genpoly[i] = rs->index_of[rs->genpoly[i]]; + + rs->users = 1; + list_add(&rs->list, &codec_list); + return rs; + +err: + kfree(rs->genpoly); + kfree(rs->index_of); + kfree(rs->alpha_to); + kfree(rs); + return NULL; +} + + +/** + * free_rs - Free the rs control structure + * @rs: The control structure which is not longer used by the + * caller + * + * Free the control structure. If @rs is the last user of the associated + * codec, free the codec as well. + */ +void free_rs(struct rs_control *rs) +{ + struct rs_codec *cd; + + if (!rs) + return; + + cd = rs->codec; + mutex_lock(&rslistlock); + cd->users--; + if(!cd->users) { + list_del(&cd->list); + kfree(cd->alpha_to); + kfree(cd->index_of); + kfree(cd->genpoly); + kfree(cd); + } + mutex_unlock(&rslistlock); + kfree(rs); +} +EXPORT_SYMBOL_GPL(free_rs); + +/** + * init_rs_internal - Allocate rs control, find a matching codec or allocate a new one + * @symsize: the symbol size (number of bits) + * @gfpoly: the extended Galois field generator polynomial coefficients, + * with the 0th coefficient in the low order bit. The polynomial + * must be primitive; + * @gffunc: pointer to function to generate the next field element, + * or the multiplicative identity element if given 0. Used + * instead of gfpoly if gfpoly is 0 + * @fcr: the first consecutive root of the rs code generator polynomial + * in index form + * @prim: primitive element to generate polynomial roots + * @nroots: RS code generator polynomial degree (number of roots) + * @gfp: GFP_ flags for allocations + */ +static struct rs_control *init_rs_internal(int symsize, int gfpoly, + int (*gffunc)(int), int fcr, + int prim, int nroots, gfp_t gfp) +{ + struct list_head *tmp; + struct rs_control *rs; + unsigned int bsize; + + /* Sanity checks */ + if (symsize < 1) + return NULL; + if (fcr < 0 || fcr >= (1<= (1<= (1<mm) + continue; + if (gfpoly != cd->gfpoly) + continue; + if (gffunc != cd->gffunc) + continue; + if (fcr != cd->fcr) + continue; + if (prim != cd->prim) + continue; + if (nroots != cd->nroots) + continue; + /* We have a matching one already */ + cd->users++; + rs->codec = cd; + goto out; + } + + /* Create a new one */ + rs->codec = codec_init(symsize, gfpoly, gffunc, fcr, prim, nroots, gfp); + if (!rs->codec) { + kfree(rs); + rs = NULL; + } +out: + mutex_unlock(&rslistlock); + return rs; +} + +/** + * init_rs_gfp - Create a RS control struct and initialize it + * @symsize: the symbol size (number of bits) + * @gfpoly: the extended Galois field generator polynomial coefficients, + * with the 0th coefficient in the low order bit. The polynomial + * must be primitive; + * @fcr: the first consecutive root of the rs code generator polynomial + * in index form + * @prim: primitive element to generate polynomial roots + * @nroots: RS code generator polynomial degree (number of roots) + * @gfp: Memory allocation flags. + */ +struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim, + int nroots, gfp_t gfp) +{ + return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots, gfp); +} +EXPORT_SYMBOL_GPL(init_rs_gfp); + +/** + * init_rs_non_canonical - Allocate rs control struct for fields with + * non-canonical representation + * @symsize: the symbol size (number of bits) + * @gffunc: pointer to function to generate the next field element, + * or the multiplicative identity element if given 0. Used + * instead of gfpoly if gfpoly is 0 + * @fcr: the first consecutive root of the rs code generator polynomial + * in index form + * @prim: primitive element to generate polynomial roots + * @nroots: RS code generator polynomial degree (number of roots) + */ +struct rs_control *init_rs_non_canonical(int symsize, int (*gffunc)(int), + int fcr, int prim, int nroots) +{ + return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots, + GFP_KERNEL); +} +EXPORT_SYMBOL_GPL(init_rs_non_canonical); + +#ifdef CONFIG_REED_SOLOMON_ENC8 +/** + * encode_rs8 - Calculate the parity for data values (8bit data width) + * @rsc: the rs control structure + * @data: data field of a given type + * @len: data length + * @par: parity data, must be initialized by caller (usually all 0) + * @invmsk: invert data mask (will be xored on data) + * + * The parity uses a uint16_t data type to enable + * symbol size > 8. The calling code must take care of encoding of the + * syndrome result for storage itself. + */ +int encode_rs8(struct rs_control *rsc, uint8_t *data, int len, uint16_t *par, + uint16_t invmsk) +{ +#include "encode_rs.c" +} +EXPORT_SYMBOL_GPL(encode_rs8); +#endif + +#ifdef CONFIG_REED_SOLOMON_DEC8 +/** + * decode_rs8 - Decode codeword (8bit data width) + * @rsc: the rs control structure + * @data: data field of a given type + * @par: received parity data field + * @len: data length + * @s: syndrome data field, must be in index form + * (if NULL, syndrome is calculated) + * @no_eras: number of erasures + * @eras_pos: position of erasures, can be NULL + * @invmsk: invert data mask (will be xored on data, not on parity!) + * @corr: buffer to store correction bitmask on eras_pos + * + * The syndrome and parity uses a uint16_t data type to enable + * symbol size > 8. The calling code must take care of decoding of the + * syndrome result and the received parity before calling this code. + * + * Note: The rs_control struct @rsc contains buffers which are used for + * decoding, so the caller has to ensure that decoder invocations are + * serialized. + * + * Returns the number of corrected symbols or -EBADMSG for uncorrectable + * 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 *corr) +{ +#include "decode_rs.c" +} +EXPORT_SYMBOL_GPL(decode_rs8); +#endif + +#ifdef CONFIG_REED_SOLOMON_ENC16 +/** + * encode_rs16 - Calculate the parity for data values (16bit data width) + * @rsc: the rs control structure + * @data: data field of a given type + * @len: data length + * @par: parity data, must be initialized by caller (usually all 0) + * @invmsk: invert data mask (will be xored on data, not on parity!) + * + * Each field in the data array contains up to symbol size bits of valid data. + */ +int encode_rs16(struct rs_control *rsc, uint16_t *data, int len, uint16_t *par, + uint16_t invmsk) +{ +#include "encode_rs.c" +} +EXPORT_SYMBOL_GPL(encode_rs16); +#endif + +#ifdef CONFIG_REED_SOLOMON_DEC16 +/** + * decode_rs16 - Decode codeword (16bit data width) + * @rsc: the rs control structure + * @data: data field of a given type + * @par: received parity data field + * @len: data length + * @s: syndrome data field, must be in index form + * (if NULL, syndrome is calculated) + * @no_eras: number of erasures + * @eras_pos: position of erasures, can be NULL + * @invmsk: invert data mask (will be xored on data, not on parity!) + * @corr: buffer to store correction bitmask on eras_pos + * + * Each field in the data array contains up to symbol size bits of valid data. + * + * Note: The rc_control struct @rsc contains buffers which are used for + * decoding, so the caller has to ensure that decoder invocations are + * serialized. + * + * Returns the number of corrected symbols or -EBADMSG for uncorrectable + * 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 *corr) +{ +#include "decode_rs.c" +} +EXPORT_SYMBOL_GPL(decode_rs16); +#endif + +MODULE_LICENSE("GPL"); +MODULE_DESCRIPTION("Reed Solomon encoder/decoder"); +MODULE_AUTHOR("Phil Karn, Thomas Gleixner"); + diff --git a/lib/reed_solomon/test_rslib.c b/lib/reed_solomon/test_rslib.c new file mode 100644 index 000000000..42b856e6c --- /dev/null +++ b/lib/reed_solomon/test_rslib.c @@ -0,0 +1,518 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Tests for Generic Reed Solomon encoder / decoder library + * + * Written by Ferdinand Blomqvist + * Based on previous work by Phil Karn, KA9Q + */ +#include +#include +#include +#include +#include +#include + +enum verbosity { + V_SILENT, + V_PROGRESS, + V_CSUMMARY +}; + +enum method { + CORR_BUFFER, + CALLER_SYNDROME, + IN_PLACE +}; + +#define __param(type, name, init, msg) \ + static type name = init; \ + module_param(name, type, 0444); \ + MODULE_PARM_DESC(name, msg) + +__param(int, v, V_PROGRESS, "Verbosity level"); +__param(int, ewsc, 1, "Erasures without symbol corruption"); +__param(int, bc, 1, "Test for correct behaviour beyond error correction capacity"); + +struct etab { + int symsize; + int genpoly; + int fcs; + int prim; + int nroots; + int ntrials; +}; + +/* List of codes to test */ +static struct etab Tab[] = { + {2, 0x7, 1, 1, 1, 100000 }, + {3, 0xb, 1, 1, 2, 100000 }, + {3, 0xb, 1, 1, 3, 100000 }, + {3, 0xb, 2, 1, 4, 100000 }, + {4, 0x13, 1, 1, 4, 10000 }, + {5, 0x25, 1, 1, 6, 1000 }, + {6, 0x43, 3, 1, 8, 1000 }, + {7, 0x89, 1, 1, 14, 500 }, + {8, 0x11d, 1, 1, 30, 100 }, + {8, 0x187, 112, 11, 32, 100 }, + {9, 0x211, 1, 1, 33, 80 }, + {0, 0, 0, 0, 0, 0}, +}; + + +struct estat { + int dwrong; + int irv; + int wepos; + int nwords; +}; + +struct bcstat { + int rfail; + int rsuccess; + int noncw; + int nwords; +}; + +struct wspace { + uint16_t *c; /* sent codeword */ + uint16_t *r; /* received word */ + uint16_t *s; /* syndrome */ + uint16_t *corr; /* correction buffer */ + int *errlocs; + int *derrlocs; +}; + +struct pad { + int mult; + int shift; +}; + +static struct pad pad_coef[] = { + { 0, 0 }, + { 1, 2 }, + { 1, 1 }, + { 3, 2 }, + { 1, 0 }, +}; + +static void free_ws(struct wspace *ws) +{ + if (!ws) + return; + + kfree(ws->errlocs); + kfree(ws->c); + kfree(ws); +} + +static struct wspace *alloc_ws(struct rs_codec *rs) +{ + int nroots = rs->nroots; + struct wspace *ws; + int nn = rs->nn; + + ws = kzalloc_obj(*ws); + if (!ws) + return NULL; + + ws->c = kmalloc_array(2 * (nn + nroots), + sizeof(uint16_t), GFP_KERNEL); + if (!ws->c) + goto err; + + ws->r = ws->c + nn; + ws->s = ws->r + nn; + ws->corr = ws->s + nroots; + + ws->errlocs = kmalloc_objs(int, nn + nroots); + if (!ws->errlocs) + goto err; + + ws->derrlocs = ws->errlocs + nn; + return ws; + +err: + free_ws(ws); + return NULL; +} + + +/* + * Generates a random codeword and stores it in c. Generates random errors and + * erasures, and stores the random word with errors in r. Erasure positions are + * stored in derrlocs, while errlocs has one of three values in every position: + * + * 0 if there is no error in this position; + * 1 if there is a symbol error in this position; + * 2 if there is an erasure without symbol corruption. + * + * Returns the number of corrupted symbols. + */ +static int get_rcw_we(struct rs_control *rs, struct wspace *ws, + int len, int errs, int eras) +{ + int nroots = rs->codec->nroots; + int *derrlocs = ws->derrlocs; + int *errlocs = ws->errlocs; + int dlen = len - nroots; + int nn = rs->codec->nn; + uint16_t *c = ws->c; + uint16_t *r = ws->r; + int errval; + int errloc; + int i; + + /* Load c with random data and encode */ + for (i = 0; i < dlen; i++) + c[i] = get_random_u32() & nn; + + memset(c + dlen, 0, nroots * sizeof(*c)); + encode_rs16(rs, c, dlen, c + dlen, 0); + + /* Make copyand add errors and erasures */ + memcpy(r, c, len * sizeof(*r)); + memset(errlocs, 0, len * sizeof(*errlocs)); + memset(derrlocs, 0, nroots * sizeof(*derrlocs)); + + /* Generating random errors */ + for (i = 0; i < errs; i++) { + do { + /* Error value must be nonzero */ + errval = get_random_u32() & nn; + } while (errval == 0); + + do { + /* Must not choose the same location twice */ + errloc = get_random_u32_below(len); + } while (errlocs[errloc] != 0); + + errlocs[errloc] = 1; + r[errloc] ^= errval; + } + + /* Generating random erasures */ + for (i = 0; i < eras; i++) { + do { + /* Must not choose the same location twice */ + errloc = get_random_u32_below(len); + } while (errlocs[errloc] != 0); + + derrlocs[i] = errloc; + + if (ewsc && get_random_u32_below(2)) { + /* Erasure with the symbol intact */ + errlocs[errloc] = 2; + } else { + /* Erasure with corrupted symbol */ + do { + /* Error value must be nonzero */ + errval = get_random_u32() & nn; + } while (errval == 0); + + errlocs[errloc] = 1; + r[errloc] ^= errval; + errs++; + } + } + + return errs; +} + +static void fix_err(uint16_t *data, int nerrs, uint16_t *corr, int *errlocs) +{ + int i; + + for (i = 0; i < nerrs; i++) + data[errlocs[i]] ^= corr[i]; +} + +static void compute_syndrome(struct rs_control *rsc, uint16_t *data, + int len, uint16_t *syn) +{ + struct rs_codec *rs = rsc->codec; + uint16_t *alpha_to = rs->alpha_to; + uint16_t *index_of = rs->index_of; + int nroots = rs->nroots; + int prim = rs->prim; + int fcr = rs->fcr; + int i, j; + + /* Calculating syndrome */ + for (i = 0; i < nroots; i++) { + syn[i] = data[0]; + for (j = 1; j < len; j++) { + if (syn[i] == 0) { + syn[i] = data[j]; + } else { + syn[i] = data[j] ^ + alpha_to[rs_modnn(rs, index_of[syn[i]] + + (fcr + i) * prim)]; + } + } + } + + /* Convert to index form */ + for (i = 0; i < nroots; i++) + syn[i] = rs->index_of[syn[i]]; +} + +/* 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, + struct wspace *ws, int method) +{ + int dlen = len - rs->codec->nroots; + int *derrlocs = ws->derrlocs; + int *errlocs = ws->errlocs; + uint16_t *corr = ws->corr; + uint16_t *c = ws->c; + uint16_t *r = ws->r; + uint16_t *s = ws->s; + int derrs, nerrs; + int i, j; + + for (j = 0; j < trials; j++) { + nerrs = get_rcw_we(rs, ws, len, errs, eras); + + switch (method) { + case CORR_BUFFER: + derrs = decode_rs16(rs, r, r + dlen, dlen, + NULL, eras, derrlocs, 0, corr); + fix_err(r, derrs, corr, derrlocs); + break; + case CALLER_SYNDROME: + compute_syndrome(rs, r, len, s); + derrs = decode_rs16(rs, NULL, NULL, dlen, + s, eras, derrlocs, 0, corr); + fix_err(r, derrs, corr, derrlocs); + break; + case IN_PLACE: + derrs = decode_rs16(rs, r, r + dlen, dlen, + NULL, eras, derrlocs, 0, NULL); + break; + default: + continue; + } + + if (derrs != nerrs) + stat->irv++; + + if (method != IN_PLACE) { + for (i = 0; i < derrs; i++) { + if (errlocs[derrlocs[i]] != 1) + stat->wepos++; + } + } + + if (memcmp(r, c, len * sizeof(*r))) + stat->dwrong++; + } + stat->nwords += trials; +} + +static int ex_rs_helper(struct rs_control *rs, struct wspace *ws, + int len, int trials, int method) +{ + static const char * const desc[] = { + "Testing correction buffer interface...", + "Testing with caller provided syndrome...", + "Testing in-place interface..." + }; + + struct estat stat = {0, 0, 0, 0}; + int nroots = rs->codec->nroots; + int errs, eras, retval; + + if (v >= V_PROGRESS) + 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); + + if (v >= V_CSUMMARY) { + pr_info(" Decodes wrong: %d / %d\n", + stat.dwrong, stat.nwords); + pr_info(" Wrong return value: %d / %d\n", + stat.irv, stat.nwords); + if (method != IN_PLACE) + pr_info(" Wrong error position: %d\n", stat.wepos); + } + + retval = stat.dwrong + stat.wepos + stat.irv; + if (retval && v >= V_PROGRESS) + pr_warn(" FAIL: %d decoding failures!\n", retval); + + return retval; +} + +static int exercise_rs(struct rs_control *rs, struct wspace *ws, + int len, int trials) +{ + + int retval = 0; + int i; + + if (v >= V_PROGRESS) + pr_info("Testing up to error correction capacity...\n"); + + for (i = 0; i <= IN_PLACE; i++) + retval |= ex_rs_helper(rs, ws, len, trials, i); + + return retval; +} + +/* 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, + struct wspace *ws) +{ + int nroots = rs->codec->nroots; + int dlen = len - nroots; + int *derrlocs = ws->derrlocs; + uint16_t *corr = ws->corr; + uint16_t *r = ws->r; + int derrs, j; + + for (j = 0; j < trials; j++) { + get_rcw_we(rs, ws, len, errs, eras); + derrs = decode_rs16(rs, r, r + dlen, dlen, + NULL, eras, derrlocs, 0, corr); + fix_err(r, derrs, corr, derrlocs); + + if (derrs >= 0) { + stat->rsuccess++; + + /* + * We check that the returned word is actually a + * codeword. The obvious way to do this would be to + * compute the syndrome, but we don't want to replicate + * that code here. However, all the codes are in + * systematic form, and therefore we can encode the + * returned word, and see whether the parity changes or + * not. + */ + memset(corr, 0, nroots * sizeof(*corr)); + encode_rs16(rs, r, dlen, corr, 0); + + if (memcmp(r + dlen, corr, nroots * sizeof(*corr))) + stat->noncw++; + } else { + stat->rfail++; + } + } + stat->nwords += trials; +} + +static int exercise_rs_bc(struct rs_control *rs, struct wspace *ws, + int len, int trials) +{ + struct bcstat stat = {0, 0, 0, 0}; + int nroots = rs->codec->nroots; + int errs, eras, cutoff; + + if (v >= V_PROGRESS) + pr_info("Testing beyond error correction capacity...\n"); + + for (errs = 1; errs <= nroots; errs++) { + eras = nroots - 2 * errs + 1; + if (eras < 0) + eras = 0; + + cutoff = nroots <= len - errs ? nroots : len - errs; + for (; eras <= cutoff; eras++) + test_bc(rs, len, errs, eras, trials, &stat, ws); + } + + if (v >= V_CSUMMARY) { + pr_info(" decoder gives up: %d / %d\n", + stat.rfail, stat.nwords); + pr_info(" decoder returns success: %d / %d\n", + stat.rsuccess, stat.nwords); + pr_info(" not a codeword: %d / %d\n", + stat.noncw, stat.rsuccess); + } + + if (stat.noncw && v >= V_PROGRESS) + pr_warn(" FAIL: %d silent failures!\n", stat.noncw); + + return stat.noncw; +} + +static int run_exercise(struct etab *e) +{ + int nn = (1 << e->symsize) - 1; + int kk = nn - e->nroots; + struct rs_control *rsc; + int retval = -ENOMEM; + int max_pad = kk - 1; + int prev_pad = -1; + struct wspace *ws; + int i; + + rsc = init_rs(e->symsize, e->genpoly, e->fcs, e->prim, e->nroots); + if (!rsc) + return retval; + + ws = alloc_ws(rsc->codec); + if (!ws) + goto err; + + retval = 0; + for (i = 0; i < ARRAY_SIZE(pad_coef); i++) { + int pad = (pad_coef[i].mult * max_pad) >> pad_coef[i].shift; + int len = nn - pad; + + if (pad == prev_pad) + continue; + + prev_pad = pad; + if (v >= V_PROGRESS) { + pr_info("Testing (%d,%d)_%d code...\n", + len, kk - pad, nn + 1); + } + + retval |= exercise_rs(rsc, ws, len, e->ntrials); + if (bc) + retval |= exercise_rs_bc(rsc, ws, len, e->ntrials); + } + + free_ws(ws); + +err: + free_rs(rsc); + return retval; +} + +static int __init test_rslib_init(void) +{ + int i, fail = 0; + + for (i = 0; Tab[i].symsize != 0 ; i++) { + int retval; + + retval = run_exercise(Tab + i); + if (retval < 0) + return -ENOMEM; + + fail |= retval; + } + + if (fail) + pr_warn("rslib: test failed\n"); + else + pr_info("rslib: test ok\n"); + + return -EAGAIN; /* Fail will directly unload the module */ +} + +static void __exit test_rslib_exit(void) +{ +} + +module_init(test_rslib_init) +module_exit(test_rslib_exit) + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Ferdinand Blomqvist"); +MODULE_DESCRIPTION("Reed-Solomon library test"); -- cgit v1.3.1