rslib: Cleanup and VLA removal

PATCH In review Thomas Gleixner 3 participants 15 messages Apr 22, 2018 – Apr 25, 2018

Subsystems (3)

Memory technology devices (MTD) Device mapper NAND flash

lore

Share & tools

lore

Thomas Gleixner

author

2018-04-22 16:23 UTC #0 lore raw

v3 cover rslib: Cleanup and VLA removal

Kees tried to get rid of the Variable Length Arrays in the Reed-Solomon library by replacing them with fixed length arrays on stack. Though they are rather large and Andrew did not fall in love with that solution.

This series addresses that in a different way by splitting the rs control structure up, so that each invocation of rs_init() returns a new instance in which the decoder buffers are allocated. The polynom tables which build the base for the RS codecs are still shareable between the instances to avoid large allocations and initializations of the same data over and over.

The usage sites have been audited and fixed up where necessary to accomodate the decoder change which forbids parallel decoder invocation for a particular rs control instance to prevent buffer corruption.

While at it the patch set tidies up the code and converts the related files over to use SPDX license identifiers.

Changes since V2:

Provide a gfp aware variant of init_rs and use it in the alloc callback of the dm/verity_fec rs_pool mempool allocations

Picked up Reviewed/Acked-by tags and fixed the subject line for the MTD specific patch.

Changes since V1:

Simplify error path in the diskonchip code and use the proper function to free the decoder.

As this spawns multiple subsystems it should either go through Andrews tree or Kees can route it with his other hardening stuff.

Thanks,

tglx

8<---------------

 drivers/md/dm-verity-fec.c        |    2 
 drivers/mtd/nand/raw/cafe_nand.c  |    7 -
 drivers/mtd/nand/raw/diskonchip.c |   67 +++++-----
 include/linux/rslib.h             |   71 +++++++----
 lib/reed_solomon/decode_rs.c      |   34 ++---
 lib/reed_solomon/encode_rs.c      |   15 --
 lib/reed_solomon/reed_solomon.c   |  233 ++++++++++++++++++++++----------------
 7 files changed, 237 insertions(+), 192 deletions(-)

Thomas Gleixner

author

2018-04-22 16:23 UTC #1 lore raw

PATCH v3 1/10 rslib: Add GFP aware init function

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 <[email protected]>

Cc Mike Snitzer <[email protected]>

Cc Alasdair Kergon <[email protected]>

Cc Neil Brown <[email protected]>

---
 include/linux/rslib.h           |   26 +++++++++++++++++++++++---
 lib/reed_solomon/reed_solomon.c |   36 ++++++++++++++++++++----------------
 2 files changed, 43 insertions(+), 19 deletions(-)

include/linux/rslib.h +23 -3

@@ -77,10 +77,30 @@ int decode_rs16(struct rs_control *rs, u
 #endif
 
 /* Create or get a matching rs control structure */
-struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim,
-			   int nroots);
+struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim,
+			       int nroots, gfp_t gfp);
+
+/**
+ * init_rs - 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)
+ *
+ * Allocations use GFP_KERNEL.
+ */
+static inline struct rs_control *init_rs(int symsize, int gfpoly, int fcr,
+					 int prim, int nroots)
+{
+	return init_rs_gfp(symsize, gfpoly, fcr, prim, nroots, GFP_KERNEL);
+}
+
 struct rs_control *init_rs_non_canonical(int symsize, int (*func)(int),
-                                         int fcr, int prim, int nroots);
+					 int fcr, int prim, int nroots);
 
 /* Release a rs control structure */
 void free_rs(struct rs_control *rs);

lib/reed_solomon/reed_solomon.c +20 ~~-16~~

@@ -59,19 +59,20 @@ static DEFINE_MUTEX(rslistlock);
  * @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 control structure and the polynom arrays for faster
  * en/decoding. Fill the arrays according to the given parameters.
  */
 static struct rs_control *rs_init(int symsize, int gfpoly, int (*gffunc)(int),
-                                  int fcr, int prim, int nroots)
+				  int fcr, int prim, int nroots, gfp_t gfp)
 {
 	struct rs_control *rs;
 	int i, j, sr, root, iprim;
 
 	/* Allocate the control structure */
-	rs = kmalloc(sizeof (struct rs_control), GFP_KERNEL);
-	if (rs == NULL)
+	rs = kmalloc(sizeof(*rs), gfp);
+	if (!rs)
 		return NULL;
 
 	INIT_LIST_HEAD(&rs->list);

@@ -85,15 +86,15 @@ static struct rs_control *rs_init(int sy
 	rs->gffunc = gffunc;
 
 	/* Allocate the arrays */
-	rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL);
+	rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), gfp);
 	if (rs->alpha_to == NULL)
 		goto errrs;
 
-	rs->index_of = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL);
+	rs->index_of = kmalloc(sizeof(uint16_t) * (rs->nn + 1), gfp);
 	if (rs->index_of == NULL)
 		goto erralp;
 
-	rs->genpoly = kmalloc(sizeof(uint16_t) * (rs->nroots + 1), GFP_KERNEL);
+	rs->genpoly = kmalloc(sizeof(uint16_t) * (rs->nroots + 1), gfp);
 	if(rs->genpoly == NULL)
 		goto erridx;

@@ -195,13 +196,14 @@ void free_rs(struct rs_control *rs)
  *		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)
+					   int (*gffunc)(int), int fcr,
+					   int prim, int nroots, gfp_t gfp)
 {
-	struct list_head	*tmp;
-	struct rs_control	*rs;
+	struct list_head *tmp;
+	struct rs_control *rs;
 
 	/* Sanity checks */
 	if (symsize < 1)

@@ -236,7 +238,7 @@ static struct rs_control *init_rs_intern
 	}
 
 	/* Create a new one */
-	rs = rs_init(symsize, gfpoly, gffunc, fcr, prim, nroots);
+	rs = rs_init(symsize, gfpoly, gffunc, fcr, prim, nroots, gfp);
 	if (rs) {
 		rs->users = 1;
 		list_add(&rs->list, &rslist);

@@ -247,7 +249,7 @@ static struct rs_control *init_rs_intern
 }
 
 /**
- * init_rs - Find a matching or allocate a new rs control structure
+ * init_rs_gfp - Find a matching or allocate a new rs control structure
  *  @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

@@ -256,11 +258,12 @@ static struct rs_control *init_rs_intern
  *		in index form
  *  @prim:	primitive element to generate polynomial roots
  *  @nroots:	RS code generator polynomial degree (number of roots)
+ *  @gfp:	GFP_ flags for allocations
  */
-struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim,
-                           int nroots)
+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);
+	return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots, gfp);
 }
 
 /**

@@ -279,7 +282,8 @@ struct rs_control *init_rs(int symsize,
 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);
+	return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots,
+				GFP_KERNEL);
 }
 
 #ifdef CONFIG_REED_SOLOMON_ENC8

Stephen Rothwell

2018-04-25 01:16 UTC #2 lore raw

Re: [patch V3 01/10] rslib: Add GFP aware init function

Hi Thomas,

Quoted 36 lines · On Sun, 22 Apr 2018 18:23:46 +0200 Thomas Gleixner <[email protected]> wrote:

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 <[email protected]>

Cc Mike Snitzer <[email protected]>

Cc Alasdair Kergon <[email protected]>

Cc Neil Brown <[email protected]>

---
 include/linux/rslib.h           |   26 +++++++++++++++++++++++---
 lib/reed_solomon/reed_solomon.c |   36 ++++++++++++++++++++----------------
 2 files changed, 43 insertions(+), 19 deletions(-)

include/linux/rslib.h +12 -2

@@ -77,10 +77,30 @@ int decode_rs16(struct rs_control *rs, u
 #endif
 
 /* Create or get a matching rs control structure */
-struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim,
-			   int nroots);
+struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim,
+			       int nroots, gfp_t gfp);
+
+/**
+ * init_rs - 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

include/linux/rslib.h int decode_rs16(struct rs_control *rs, u · line 101

Quoted 10 lines

include/linux/rslib.h +10 -0

+ *  @nroots:	RS code generator polynomial degree (number of roots)
+ *
+ * Allocations use GFP_KERNEL.
+ */
+static inline struct rs_control *init_rs(int symsize, int gfpoly, int fcr,
+					 int prim, int nroots)
+{
+	return init_rs_gfp(symsize, gfpoly, fcr, prim, nroots, GFP_KERNEL);
+}
+

The version of this patch that Kees has committed to his kspp tree in linux-next has

#include <linux/slab.h>

why not just

#include <linux/types.h> /* for gpf_t */
#include <linux/gpf.h> /* for GFP_KERNEL */

Signature · 2 lines

Cheers,
Stephen Rothwell

Kees Cook

2018-04-25 02:45 UTC #3 lore raw

Re: [patch V3 01/10] rslib: Add GFP aware init function

Quoted 52 lines · Stephen Rothwell

Hi Thomas,

Quoted 36 lines · On Sun, 22 Apr 2018 18:23:46 +0200 Thomas Gleixner <[email protected]> wrote:

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 <[email protected]>

Cc Mike Snitzer <[email protected]>

Cc Alasdair Kergon <[email protected]>

Cc Neil Brown <[email protected]>

---
 include/linux/rslib.h           |   26 +++++++++++++++++++++++---
 lib/reed_solomon/reed_solomon.c |   36 ++++++++++++++++++++----------------
 2 files changed, 43 insertions(+), 19 deletions(-)

include/linux/rslib.h +12 -2

@@ -77,10 +77,30 @@ int decode_rs16(struct rs_control *rs, u
 #endif
 
 /* Create or get a matching rs control structure */
-struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim,
-                        int nroots);
+struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim,
+                            int nroots, gfp_t gfp);
+
+/**
+ * init_rs - 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

include/linux/rslib.h int decode_rs16(struct rs_control *rs, u · line 101

Quoted 10 lines

include/linux/rslib.h +10 -0

+ *  @nroots: RS code generator polynomial degree (number of roots)
+ *
+ * Allocations use GFP_KERNEL.
+ */
+static inline struct rs_control *init_rs(int symsize, int gfpoly, int fcr,
+                                      int prim, int nroots)
+{
+     return init_rs_gfp(symsize, gfpoly, fcr, prim, nroots, GFP_KERNEL);
+}
+

The version of this patch that Kees has committed to his kspp tree in linux-next has

Quoted 8 lines

#include <linux/slab.h>
why not just
#include <linux/types.h> /* for gpf_t */
#include <linux/gpf.h> /* for GFP_KERNEL */
?

We could certainly switch to that. (Why doesn't gfp.h include types.h?)

-Kees

Signature · 2 lines

Kees Cook
Pixel Security

Thomas Gleixner

author

2018-04-25 08:59 UTC #4 lore raw

Re: [patch V3 01/10] rslib: Add GFP aware init function

Quoted 11 lines · Kees Cook

Quoted 10 lines · Stephen Rothwell
include/linux/rslib.h int decode_rs16(struct rs_control *rs, u · line 101
Quoted 6 lines · On Sun, 22 Apr 2018 18:23:46 +0200 Thomas Gleixner <[email protected]> wrote:
include/linux/rslib.h +6 -0
+static inline struct rs_control *init_rs(int symsize, int gfpoly, int fcr,
+                                      int prim, int nroots)
+{
+     return init_rs_gfp(symsize, gfpoly, fcr, prim, nroots, GFP_KERNEL);
+}
+
The version of this patch that Kees has committed to his kspp tree in linux-next has

Quoted 8 lines

Quoted 8 lines
#include <linux/slab.h>
why not just
#include <linux/types.h> /* for gpf_t */
#include <linux/gpf.h> /* for GFP_KERNEL */
?

Sure

Quoted 1 line

We could certainly switch to that. (Why doesn't gfp.h include types.h?)

Excellent question.

Thanks,

tglx

Thomas Gleixner

author

2018-04-22 16:23 UTC #5 lore raw

PATCH v3 2/10 dm/verity_fec: Use GFP aware reed solomon init

In reply to Thomas Gleixner

Allocations from the rs_pool can invoke init_rs() from the mempool allocation callback. This is problematic in fec_alloc_bufs() which invokes mempool_alloc() with GFP_NOIO to prevent a swap deadlock because init_rs() uses GFP_KERNEL allocations.

Switch it to init_rs_gfp() and invoke it with the gfp_t flags which are handed in from the allocator.

Note: This is not a problem today because the rs control struct is shared between the instances and its created when the mempool is initialized. But the upcoming changes which switch to a rs_control struct per instance to embed decoder buffers will trigger the swap vs. GFP_KERNEL issue.

Signed-off-by Thomas Gleixner <[email protected]>

Cc Mike Snitzer <[email protected]>

Cc Alasdair Kergon <[email protected]>

Cc Neil Brown <[email protected]>

---
 drivers/md/dm-verity-fec.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

drivers/md/dm-verity-fec.c +1 -1

@@ -570,7 +570,7 @@ static void *fec_rs_alloc(gfp_t gfp_mask
 {
 	struct dm_verity *v = (struct dm_verity *)pool_data;
 
-	return init_rs(8, 0x11d, 0, 1, v->fec->roots);
+	return init_rs_gfp(8, 0x11d, 0, 1, v->fec->roots, gfp_mask);
 }
 
 static void fec_rs_free(void *element, void *pool_data)

Thomas Gleixner

author

2018-04-22 16:23 UTC #6 lore raw

PATCH v3 3/10 rslib: Cleanup whitespace damage

In reply to Thomas Gleixner

From: Thomas Gleixner <[email protected]>

Instead of mixing the whitespace cleanup into functional changes, mop it up first.

Signed-off-by Thomas Gleixner <[email protected]>

Cc Boris Brezillon <[email protected]>

Cc Tony Luck <[email protected]>

Cc Kees Cook <[email protected]>

Cc Segher Boessenkool <[email protected]>

Cc Kernel Hardening <[email protected]>

Cc Richard Weinberger <[email protected]>

Cc Mike Snitzer <[email protected]>

Cc Anton Vorontsov <[email protected]>

Cc Colin Cross <[email protected]>

Cc Andrew Morton <[email protected]>

Cc David Woodhouse <[email protected]>

Cc Alasdair Kergon <[email protected]>

---
 include/linux/rslib.h           |   12 ++++++------
 lib/reed_solomon/reed_solomon.c |   12 ++++++------
 2 files changed, 12 insertions(+), 12 deletions(-)

include/linux/rslib.h +6 -6

@@ -39,15 +39,15 @@
  * @list:	List entry for the rs control list
 */
 struct rs_control {
-	int 		mm;
-	int 		nn;
+	int		mm;
+	int		nn;
 	uint16_t	*alpha_to;
 	uint16_t	*index_of;
 	uint16_t	*genpoly;
-	int 		nroots;
-	int 		fcr;
-	int 		prim;
-	int 		iprim;
+	int		nroots;
+	int		fcr;
+	int		prim;
+	int		iprim;
 	int		gfpoly;
 	int		(*gffunc)(int);
 	int		users;

lib/reed_solomon/reed_solomon.c +6 -6

@@ -192,7 +192,7 @@ void free_rs(struct rs_control *rs)
  *  @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
+ *  @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)

@@ -209,9 +209,9 @@ static struct rs_control *init_rs_intern
 	if (symsize < 1)
 		return NULL;
 	if (fcr < 0 || fcr >= (1<<symsize))
-    		return NULL;
+		return NULL;
 	if (prim <= 0 || prim >= (1<<symsize))
-    		return NULL;
+		return NULL;
 	if (nroots < 0 || nroots >= (1<<symsize))
 		return NULL;

@@ -254,7 +254,7 @@ static struct rs_control *init_rs_intern
  *  @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
+ *  @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)

@@ -274,13 +274,13 @@ struct rs_control *init_rs_gfp(int symsi
  *  @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
+ *  @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)
+					 int fcr, int prim, int nroots)
 {
 	return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots,
 				GFP_KERNEL);

Thomas Gleixner

author

2018-04-22 16:23 UTC #7 lore raw

PATCH v3 4/10 rslib: Cleanup top level comments

In reply to Thomas Gleixner

From: Thomas Gleixner <[email protected]>

File references and stale CVS ids are really not useful.

Signed-off-by Thomas Gleixner <[email protected]>

Cc Boris Brezillon <[email protected]>

Cc Tony Luck <[email protected]>

Cc Kees Cook <[email protected]>

Cc Segher Boessenkool <[email protected]>

Cc Kernel Hardening <[email protected]>

Cc Richard Weinberger <[email protected]>

Cc Mike Snitzer <[email protected]>

Cc Anton Vorontsov <[email protected]>

Cc Colin Cross <[email protected]>

Cc Andrew Morton <[email protected]>

Cc David Woodhouse <[email protected]>

Cc Alasdair Kergon <[email protected]>

---
 include/linux/rslib.h           |    7 +------
 lib/reed_solomon/decode_rs.c    |   12 ++----------
 lib/reed_solomon/encode_rs.c    |   13 ++-----------
 lib/reed_solomon/reed_solomon.c |    9 +--------
 4 files changed, 6 insertions(+), 35 deletions(-)

include/linux/rslib.h +1 -6

@@ -1,16 +1,11 @@
 /*
- * include/linux/rslib.h
- *
- * Overview:
- *   Generic Reed Solomon encoder / decoder library
+ * Generic Reed Solomon encoder / decoder library
  *
  * Copyright (C) 2004 Thomas Gleixner ([email protected])
  *
  * RS code lifted from reed solomon library written by Phil Karn
  * Copyright 2002 Phil Karn, KA9Q
  *
- * $Id: rslib.h,v 1.4 2005/11/07 11:14:52 gleixner Exp $
- *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 2 as
  * published by the Free Software Foundation.

lib/reed_solomon/decode_rs.c +2 ~~-10~~

@@ -1,20 +1,12 @@
 /*
- * lib/reed_solomon/decode_rs.c
- *
- * Overview:
- *   Generic Reed Solomon encoder / decoder library
+ * 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 ([email protected])
  *
- * $Id: decode_rs.c,v 1.7 2005/11/07 11:14:59 gleixner Exp $
- *
- */
-
-/* Generic data width independent code which is included by the
- * wrappers.
+ * Generic data width independent code which is included by the wrappers.
  */
 {
 	int deg_lambda, el, deg_omega;

lib/reed_solomon/encode_rs.c +2 ~~-11~~

@@ -1,21 +1,12 @@
 /*
- * lib/reed_solomon/encode_rs.c
- *
- * Overview:
- *   Generic Reed Solomon encoder / decoder library
+ * 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 ([email protected])
  *
- * $Id: encode_rs.c,v 1.5 2005/11/07 11:14:59 gleixner Exp $
- *
- */
-
-/* Generic data width independent code which is included by the
- * wrappers.
- * int encode_rsX (struct rs_control *rs, uintX_t *data, int len, uintY_t *par)
+ * Generic data width independent code which is included by the wrappers.
  */
 {
 	int i, j, pad;

lib/reed_solomon/reed_solomon.c +1 -8

@@ -1,16 +1,11 @@
 /*
- * lib/reed_solomon/reed_solomon.c
- *
- * Overview:
- *   Generic Reed Solomon encoder / decoder library
+ * Generic Reed Solomon encoder / decoder library
  *
  * Copyright (C) 2004 Thomas Gleixner ([email protected])
  *
  * Reed Solomon code lifted from reed solomon library written by Phil Karn
  * Copyright 2002 Phil Karn, KA9Q
  *
- * $Id: rslib.c,v 1.7 2005/11/07 11:14:59 gleixner Exp $
- *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 2 as
  * published by the Free Software Foundation.

@@ -35,9 +30,7 @@
  * 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 <linux/errno.h>
 #include <linux/kernel.h>
 #include <linux/init.h>

Thomas Gleixner

author

2018-04-22 16:23 UTC #8 lore raw

PATCH v3 5/10 rslib: Add SPDX identifiers

In reply to Thomas Gleixner

From: Thomas Gleixner <[email protected]>

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 <[email protected]>

Signed-off-by David Woodhouse <[email protected]>

"No objections at all. Just keep the authorship notices." -- Phil Karn

Add the proper SPDX identifiers according to
Documentation/process/license-rules.rst.

Signed-off-by Thomas Gleixner <[email protected]>

Reviewed-by Kate Stewart <[email protected]>

Reviewed-by Greg Kroah-Hartman <[email protected]>

Cc Boris Brezillon <[email protected]>

Cc Tony Luck <[email protected]>

Cc Kees Cook <[email protected]>

Cc Segher Boessenkool <[email protected]>

Cc Kernel Hardening <[email protected]>

Cc Richard Weinberger <[email protected]>

Cc Mike Snitzer <[email protected]>

Cc Anton Vorontsov <[email protected]>

Cc Colin Cross <[email protected]>

Cc Andrew Morton <[email protected]>

Cc David Woodhouse <[email protected]>

Cc Alasdair Kergon <[email protected]>

---
 include/linux/rslib.h           |    1 +
 lib/reed_solomon/decode_rs.c    |    1 +
 lib/reed_solomon/encode_rs.c    |    1 +
 lib/reed_solomon/reed_solomon.c |    1 +
 4 files changed, 4 insertions(+)

include/linux/rslib.h +1 -0

@@ -1,3 +1,4 @@
+// SPDX-License-Identifier: GPL-2.0
 /*
  * Generic Reed Solomon encoder / decoder library
  *

lib/reed_solomon/decode_rs.c +1 -0

@@ -1,3 +1,4 @@
+// SPDX-License-Identifier: GPL-2.0
 /*
  * Generic Reed Solomon encoder / decoder library
  *

lib/reed_solomon/encode_rs.c +1 -0

@@ -1,3 +1,4 @@
+// SPDX-License-Identifier: GPL-2.0
 /*
  * Generic Reed Solomon encoder / decoder library
  *

lib/reed_solomon/reed_solomon.c +1 -0

@@ -1,3 +1,4 @@
+// SPDX-License-Identifier: GPL-2.0
 /*
  * Generic Reed Solomon encoder / decoder library
  *

Thomas Gleixner

author

2018-04-22 16:23 UTC #9 lore raw

PATCH v3 6/10 rslib: Remove GPL boilerplate

In reply to Thomas Gleixner

From: Thomas Gleixner <[email protected]>

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 <[email protected]>

Reviewed-by Kate Stewart <[email protected]>

Reviewed-by Greg Kroah-Hartman <[email protected]>

Cc Boris Brezillon <[email protected]>

Cc Tony Luck <[email protected]>

Cc Kees Cook <[email protected]>

Cc Segher Boessenkool <[email protected]>

Cc Kernel Hardening <[email protected]>

Cc Richard Weinberger <[email protected]>

Cc Mike Snitzer <[email protected]>

Cc Anton Vorontsov <[email protected]>

Cc Colin Cross <[email protected]>

Cc Andrew Morton <[email protected]>

Cc David Woodhouse <[email protected]>

Cc Alasdair Kergon <[email protected]>

---
 include/linux/rslib.h           |    5 -----
 lib/reed_solomon/reed_solomon.c |    4 ----
 2 files changed, 9 deletions(-)

include/linux/rslib.h +0 -5

@@ -6,12 +6,7 @@
  *
  * RS code lifted from reed solomon library written by Phil Karn
  * Copyright 2002 Phil Karn, KA9Q
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation.
  */
-
 #ifndef _RSLIB_H_
 #define _RSLIB_H_

lib/reed_solomon/reed_solomon.c +0 -4

@@ -7,10 +7,6 @@
  * Reed Solomon code lifted from reed solomon library written by Phil Karn
  * Copyright 2002 Phil Karn, KA9Q
  *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation.
- *
  * Description:
  *
  * The generic Reed Solomon library provides runtime configurable

Thomas Gleixner

author

2018-04-22 16:23 UTC #10 lore raw

PATCH v3 7/10 rslib: Simplify error path

In reply to Thomas Gleixner

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 <[email protected]>

---
 lib/reed_solomon/reed_solomon.c |   17 ++++++-----------
 1 file changed, 6 insertions(+), 11 deletions(-)

lib/reed_solomon/reed_solomon.c +6 ~~-11~~

@@ -60,8 +60,7 @@ static struct rs_control *rs_init(int sy
 	struct rs_control *rs;
 	int i, j, sr, root, iprim;
 
-	/* Allocate the control structure */
-	rs = kmalloc(sizeof(*rs), gfp);
+	rs = kzalloc(sizeof(*rs), gfp);
 	if (!rs)
 		return NULL;

@@ -78,15 +77,15 @@ static struct rs_control *rs_init(int sy
 	/* Allocate the arrays */
 	rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), gfp);
 	if (rs->alpha_to == NULL)
-		goto errrs;
+		goto err;
 
 	rs->index_of = kmalloc(sizeof(uint16_t) * (rs->nn + 1), gfp);
 	if (rs->index_of == NULL)
-		goto erralp;
+		goto err;
 
 	rs->genpoly = kmalloc(sizeof(uint16_t) * (rs->nroots + 1), gfp);
 	if(rs->genpoly == NULL)
-		goto erridx;
+		goto err;
 
 	/* Generate Galois field lookup tables */
 	rs->index_of[0] = rs->nn;	/* log(zero) = -inf */

@@ -111,7 +110,7 @@ static struct rs_control *rs_init(int sy
 	}
 	/* If it's not primitive, exit */
 	if(sr != rs->alpha_to[0])
-		goto errpol;
+		goto err;
 
 	/* Find prim-th root of 1, used in decoding */
 	for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn);

@@ -141,14 +140,10 @@ static struct rs_control *rs_init(int sy
 		rs->genpoly[i] = rs->index_of[rs->genpoly[i]];
 	return rs;
 
-	/* Error exit */
-errpol:
+err:
 	kfree(rs->genpoly);
-erridx:
 	kfree(rs->index_of);
-erralp:
 	kfree(rs->alpha_to);
-errrs:
 	kfree(rs);
 	return NULL;
 }

Thomas Gleixner

author

2018-04-22 16:23 UTC #11 lore raw

PATCH v3 8/10 rslib: Split rs control struct

In reply to Thomas Gleixner

From: Thomas Gleixner <[email protected]>

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 <[email protected]>

Acked-by Boris Brezillon <[email protected]>

Cc Tony Luck <[email protected]>

Cc Kees Cook <[email protected]>

Cc Segher Boessenkool <[email protected]>

Cc Kernel Hardening <[email protected]>

Cc Richard Weinberger <[email protected]>

Cc Mike Snitzer <[email protected]>

Cc Anton Vorontsov <[email protected]>

Cc Colin Cross <[email protected]>

Cc Andrew Morton <[email protected]>

Cc David Woodhouse <[email protected]>

Cc Alasdair Kergon <[email protected]>

---
 drivers/mtd/nand/raw/cafe_nand.c  |    7 +
 drivers/mtd/nand/raw/diskonchip.c |    7 +
 include/linux/rslib.h             |   19 +++--
 lib/reed_solomon/decode_rs.c      |    1 
 lib/reed_solomon/encode_rs.c      |    1 
 lib/reed_solomon/reed_solomon.c   |  135 +++++++++++++++++++++-----------------
 6 files changed, 100 insertions(+), 70 deletions(-)

drivers/mtd/nand/raw/cafe_nand.c +4 -3

@@ -394,12 +394,13 @@ static int cafe_nand_read_page(struct mt
 
 		for (i=0; i<8; i+=2) {
 			uint32_t tmp = cafe_readl(cafe, NAND_ECC_SYN01 + (i*2));
-			syn[i] = cafe->rs->index_of[tmp & 0xfff];
-			syn[i+1] = cafe->rs->index_of[(tmp >> 16) & 0xfff];
+
+			syn[i] = cafe->rs->codec->index_of[tmp & 0xfff];
+			syn[i+1] = cafe->rs->codec->index_of[(tmp >> 16) & 0xfff];
 		}
 
 		n = decode_rs16(cafe->rs, NULL, NULL, 1367, syn, 0, pos, 0,
-		                pat);
+				pat);
 
 		for (i = 0; i < n; i++) {
 			int p = pos[i];

drivers/mtd/nand/raw/diskonchip.c +4 -3

@@ -140,6 +140,7 @@ static int doc_ecc_decode(struct rs_cont
 	int i, j, nerr, errpos[8];
 	uint8_t parity;
 	uint16_t ds[4], s[5], tmp, errval[8], syn[4];
+	struct rs_codec *cd = rs->codec;
 
 	memset(syn, 0, sizeof(syn));
 	/* Convert the ecc bytes into words */

@@ -160,15 +161,15 @@ static int doc_ecc_decode(struct rs_cont
 	for (j = 1; j < NROOTS; j++) {
 		if (ds[j] == 0)
 			continue;
-		tmp = rs->index_of[ds[j]];
+		tmp = cd->index_of[ds[j]];
 		for (i = 0; i < NROOTS; i++)
-			s[i] ^= rs->alpha_to[rs_modnn(rs, tmp + (FCR + i) * j)];
+			s[i] ^= cd->alpha_to[rs_modnn(cd, tmp + (FCR + i) * j)];
 	}
 
 	/* Calc syn[i] = s[i] / alpha^(v + i) */
 	for (i = 0; i < NROOTS; i++) {
 		if (s[i])
-			syn[i] = rs_modnn(rs, rs->index_of[s[i]] + (NN - FCR - i));
+			syn[i] = rs_modnn(cd, cd->index_of[s[i]] + (NN - FCR - i));
 	}
 	/* Call the decoder library */
 	nerr = decode_rs16(rs, NULL, NULL, 1019, syn, 0, errpos, 0, errval);

include/linux/rslib.h +13 -6

@@ -13,7 +13,7 @@
 #include <linux/list.h>
 
 /**
- * struct rs_control - rs control structure
+ * struct rs_codec - rs codec data
  *
  * @mm:		Bits per symbol
  * @nn:		Symbols per block (= (1<<mm)-1)

@@ -27,9 +27,9 @@
  * @gfpoly:	The primitive generator polynominal
  * @gffunc:	Function to generate the field, if non-canonical representation
  * @users:	Users of this structure
- * @list:	List entry for the rs control list
+ * @list:	List entry for the rs codec list
 */
-struct rs_control {
+struct rs_codec {
 	int		mm;
 	int		nn;
 	uint16_t	*alpha_to;

@@ -45,6 +45,14 @@ struct rs_control {
 	struct list_head list;
 };
 
+/**
+ * struct rs_control - rs control structure per instance
+ * @codec:	The codec used for this instance
+ */
+struct rs_control {
+	struct rs_codec	*codec;
+};
+
 /* General purpose RS codec, 8-bit data width, symbol width 1-15 bit  */
 #ifdef CONFIG_REED_SOLOMON_ENC8
 int encode_rs8(struct rs_control *rs, uint8_t *data, int len, uint16_t *par,

@@ -67,7 +75,6 @@ int decode_rs16(struct rs_control *rs, u
 		uint16_t *corr);
 #endif
 
-/* Create or get a matching rs control structure */
 struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim,
 			       int nroots, gfp_t gfp);

@@ -98,7 +105,7 @@ void free_rs(struct rs_control *rs);
 
 /** modulo replacement for galois field arithmetics
  *
- *  @rs:	the rs control structure
+ *  @rs:	Pointer to the RS codec
  *  @x:		the value to reduce
  *
  *  where

@@ -108,7 +115,7 @@ void free_rs(struct rs_control *rs);
  *  Simple arithmetic modulo would return a wrong result for values
  *  >= 3 * rs->nn
 */
-static inline int rs_modnn(struct rs_control *rs, int x)
+static inline int rs_modnn(struct rs_codec *rs, int x)
 {
 	while (x >= rs->nn) {
 		x -= rs->nn;

lib/reed_solomon/decode_rs.c +1 -0

@@ -10,6 +10,7 @@
  * 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;

lib/reed_solomon/encode_rs.c +1 -0

@@ -10,6 +10,7 @@
  * 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;

lib/reed_solomon/reed_solomon.c +77 ~~-58~~

263 lines not on this page · raw message

Thomas Gleixner

author

2018-04-22 16:23 UTC #12 lore raw

PATCH v3 9/10 mtd: rawnand: diskonchip: Allocate rs control per instance

In reply to Thomas Gleixner

From: Thomas Gleixner <[email protected]>

The reed solomon library is moving the on stack decoder buffers into the rs control structure. That would break the DoC driver because multiple instances share the same control structure and can operate in parallel. At least in theory....

Instantiate a rs control instance per DoC device to avoid that. The per instance buffer is fine as the operation on a single DoC instance is serialized by the MTD/NAND core.

Signed-off-by Thomas Gleixner <[email protected]>

Acked-by Boris Brezillon <[email protected]>

Cc Tony Luck <[email protected]>

Cc Kees Cook <[email protected]>

Cc Segher Boessenkool <[email protected]>

Cc Kernel Hardening <[email protected]>

Cc Richard Weinberger <[email protected]>

Cc Mike Snitzer <[email protected]>

Cc Anton Vorontsov <[email protected]>

Cc Colin Cross <[email protected]>

Cc Andrew Morton <[email protected]>

Cc David Woodhouse <[email protected]>

Cc Alasdair Kergon <[email protected]>

---
 drivers/mtd/nand/raw/diskonchip.c |   60 +++++++++++++++++---------------------
 1 file changed, 27 insertions(+), 33 deletions(-)

drivers/mtd/nand/raw/diskonchip.c +27 ~~-33~~

@@ -66,6 +66,7 @@ struct doc_priv {
 	int curchip;
 	int mh0_page;
 	int mh1_page;
+	struct rs_control *rs_decoder;
 	struct mtd_info *nextdoc;
 
 	/* Handle the last stage of initialization (BBT scan, partitioning) */

@@ -123,9 +124,6 @@ MODULE_PARM_DESC(doc_config_location, "P
 /* Number of symbols */
 #define NN 1023
 
-/* the Reed Solomon control structure */
-static struct rs_control *rs_decoder;
-
 /*
  * The HW decoder in the DoC ASIC's provides us a error syndrome,
  * which we must convert to a standard syndrome usable by the generic

@@ -931,7 +929,7 @@ static int doc200x_correct_data(struct m
 				calc_ecc[i] = ReadDOC_(docptr, DoC_ECCSyndrome0 + i);
 		}
 
-		ret = doc_ecc_decode(rs_decoder, dat, calc_ecc);
+		ret = doc_ecc_decode(doc->rs_decoder, dat, calc_ecc);
 		if (ret > 0)
 			pr_err("doc200x_correct_data corrected %d errors\n",
 			       ret);

@@ -1422,10 +1420,10 @@ static inline int __init doc2001plus_ini
 
 static int __init doc_probe(unsigned long physadr)
 {
+	struct nand_chip *nand = NULL;
+	struct doc_priv *doc = NULL;
 	unsigned char ChipID;
 	struct mtd_info *mtd;
-	struct nand_chip *nand;
-	struct doc_priv *doc;
 	void __iomem *virtadr;
 	unsigned char save_control;
 	unsigned char tmp, tmpb, tmpc;

@@ -1562,8 +1560,25 @@ static int __init doc_probe(unsigned lon
 		goto fail;
 	}
 
+
+	/*
+	 * Allocate a RS codec instance
+	 *
+	 * Symbolsize is 10 (bits)
+	 * Primitve polynomial is x^10+x^3+1
+	 * First consecutive root is 510
+	 * Primitve element to generate roots = 1
+	 * Generator polinomial degree = 4
+	 */
+	doc = (struct doc_priv *) (nand + 1);
+	doc->rs_decoder = init_rs(10, 0x409, FCR, 1, NROOTS);
+	if (!doc->rs_decoder) {
+		pr_err("DiskOnChip: Could not create a RS codec\n");
+		ret = -ENOMEM;
+		goto fail;
+	}
+
 	mtd			= nand_to_mtd(nand);
-	doc			= (struct doc_priv *) (nand + 1);
 	nand->bbt_td		= (struct nand_bbt_descr *) (doc + 1);
 	nand->bbt_md		= nand->bbt_td + 1;

@@ -1613,7 +1628,6 @@ static int __init doc_probe(unsigned lon
 		   haven't yet added it.  This is handled without incident by
 		   mtd_device_unregister, as far as I can tell. */
 		nand_release(mtd);
-		kfree(nand);
 		goto fail;
 	}

@@ -1626,6 +1640,9 @@ static int __init doc_probe(unsigned lon
 	   actually a DiskOnChip.  */
 	WriteDOC(save_control, virtadr, DOCControl);
  fail:
+	if (doc)
+		free_rs(doc->rs_decoder);
+	kfree(nand);
 	iounmap(virtadr);
 
 error_ioremap:

@@ -1648,6 +1665,7 @@ static void release_nanddoc(void)
 		nand_release(mtd);
 		iounmap(doc->virtadr);
 		release_mem_region(doc->physadr, DOC_IOREMAP_LEN);
+		free_rs(doc->rs_decoder);
 		kfree(nand);
 	}
 }

@@ -1656,27 +1674,12 @@ static int __init init_nanddoc(void)
 {
 	int i, ret = 0;
 
-	/* We could create the decoder on demand, if memory is a concern.
-	 * This way we have it handy, if an error happens
-	 *
-	 * Symbolsize is 10 (bits)
-	 * Primitve polynomial is x^10+x^3+1
-	 * first consecutive root is 510
-	 * primitve element to generate roots = 1
-	 * generator polinomial degree = 4
-	 */
-	rs_decoder = init_rs(10, 0x409, FCR, 1, NROOTS);
-	if (!rs_decoder) {
-		pr_err("DiskOnChip: Could not create a RS decoder\n");
-		return -ENOMEM;
-	}
-
 	if (doc_config_location) {
 		pr_info("Using configured DiskOnChip probe address 0x%lx\n",
 			doc_config_location);
 		ret = doc_probe(doc_config_location);
 		if (ret < 0)
-			goto outerr;
+			return ret;
 	} else {
 		for (i = 0; (doc_locations[i] != 0xffffffff); i++) {
 			doc_probe(doc_locations[i]);

@@ -1687,11 +1690,7 @@ static int __init init_nanddoc(void)
 	if (!doclist) {
 		pr_info("No valid DiskOnChip devices found\n");
 		ret = -ENODEV;
-		goto outerr;
 	}
-	return 0;
- outerr:
-	free_rs(rs_decoder);
 	return ret;
 }

@@ -1699,11 +1698,6 @@ static void __exit cleanup_nanddoc(void)
 {
 	/* Cleanup the nand/DoC resources */
 	release_nanddoc();
-
-	/* Free the reed solomon resources */
-	if (rs_decoder) {
-		free_rs(rs_decoder);
-	}
 }
 
 module_init(init_nanddoc);

Thomas Gleixner

author

2018-04-22 16:23 UTC #13 lore raw

PATCH v3 10/10 rslib: Allocate decoder buffers to avoid VLAs

In reply to Thomas Gleixner

From: Thomas Gleixner <[email protected]>

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 <[email protected]>

Acked-by Kees Cook <[email protected]>

Cc Boris Brezillon <[email protected]>

Cc Tony Luck <[email protected]>

Cc Segher Boessenkool <[email protected]>

Cc Kernel Hardening <[email protected]>

Cc Richard Weinberger <[email protected]>

Cc Mike Snitzer <[email protected]>

Cc Anton Vorontsov <[email protected]>

Cc Colin Cross <[email protected]>

Cc Andrew Morton <[email protected]>

Cc David Woodhouse <[email protected]>

Cc Alasdair Kergon <[email protected]>

---
 include/linux/rslib.h           |    1 +
 lib/reed_solomon/decode_rs.c    |   20 +++++++++++++-------
 lib/reed_solomon/reed_solomon.c |   31 ++++++++++++++++++++++++++++++-
 3 files changed, 44 insertions(+), 8 deletions(-)

include/linux/rslib.h +1 -0

@@ -51,6 +51,7 @@ struct rs_codec {
  */
 struct rs_control {
 	struct rs_codec	*codec;
+	uint16_t	buffers[0];
 };
 
 /* General purpose RS codec, 8-bit data width, symbol width 1-15 bit  */

lib/reed_solomon/decode_rs.c +13 -7

@@ -21,16 +21,22 @@
 	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;
-	/* Err+Eras Locator poly and syndrome poly The maximum value
-	 * of nroots is 8. So the necessary stack size will be about
-	 * 220 bytes max.
-	 */
-	uint16_t lambda[nroots + 1], syn[nroots];
-	uint16_t b[nroots + 1], t[nroots + 1], omega[nroots + 1];
-	uint16_t root[nroots], reg[nroots + 1], loc[nroots];
 	int count = 0;
 	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);

lib/reed_solomon/reed_solomon.c +30 -1

@@ -37,6 +37,18 @@
 #include <linux/slab.h>
 #include <linux/mutex.h>
 
+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 */

@@ -203,6 +215,7 @@ static struct rs_control *init_rs_intern
 {
 	struct list_head *tmp;
 	struct rs_control *rs;
+	unsigned int bsize;
 
 	/* Sanity checks */
 	if (symsize < 1)

@@ -214,7 +227,13 @@ static struct rs_control *init_rs_intern
 	if (nroots < 0 || nroots >= (1<<symsize))
 		return NULL;
 
-	rs = kzalloc(sizeof(*rs), GFP_KERNEL);
+	/*
+	 * The decoder needs buffers in each control struct instance to
+	 * avoid variable size or large fixed size allocations on
+	 * stack. Size the buffers to arrays of [nroots + 1].
+	 */
+	bsize = sizeof(uint16_t) * RS_DECODE_NUM_BUFFERS * (nroots + 1);
+	rs = kzalloc(sizeof(*rs) + bsize, gfp);
 	if (!rs)
 		return NULL;

@@ -327,6 +346,11 @@ EXPORT_SYMBOL_GPL(encode_rs8);
  *  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 bits or -EBADMSG for uncorrectable errors.
  */
 int decode_rs8(struct rs_control *rsc, uint8_t *data, uint16_t *par, int len,

@@ -371,6 +395,11 @@ EXPORT_SYMBOL_GPL(encode_rs16);
  *  @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 bits or -EBADMSG for uncorrectable errors.
  */
 int decode_rs16(struct rs_control *rsc, uint16_t *data, uint16_t *par, int len,

Kees Cook

2018-04-24 16:42 UTC #14 lore raw

In reply to Thomas Gleixner

Quoted 17 lines · Thomas Gleixner

Kees tried to get rid of the Variable Length Arrays in the Reed-Solomon library by replacing them with fixed length arrays on stack. Though they are rather large and Andrew did not fall in love with that solution.
This series addresses that in a different way by splitting the rs control structure up, so that each invocation of rs_init() returns a new instance in which the decoder buffers are allocated. The polynom tables which build the base for the RS codecs are still shareable between the instances to avoid large allocations and initializations of the same data over and over.
The usage sites have been audited and fixed up where necessary to accomodate the decoder change which forbids parallel decoder invocation for a particular rs control instance to prevent buffer corruption.
While at it the patch set tidies up the code and converts the related files over to use SPDX license identifiers.

Quoted 7 lines

Changes since V2:
Provide a gfp aware variant of init_rs and use it in the alloc callback of the dm/verity_fec rs_pool mempool allocations
Picked up Reviewed/Acked-by tags and fixed the subject line for the MTD specific patch.

Excellent, thanks!

Quoted 7 lines

Changes since V1:
Simplify error path in the diskonchip code and use the proper function to free the decoder.
As this spawns multiple subsystems it should either go through Andrews tree or Kees can route it with his other hardening stuff.

I'll create a VLA sub-tree to my KSPP stuff and start collecting this and other VLA fixes that maintainers haven't taken yet. Once build-testing finishes, I'll push it out for -next.

-Kees

Signature · 2 lines

Kees Cook
Pixel Security