scatterlist: add new capabilities

lib/scatterlist.c +7 -4

index a59778946404..4986545beef9 100644
+++ b/lib/scatterlist.c

@@ -554,13 +554,15 @@ EXPORT_SYMBOL(sg_alloc_table_from_pages);
 #ifdef CONFIG_SGL_ALLOC
 
 /**
- * sgl_alloc_order - allocate a scatterlist and its pages
+ * sgl_alloc_order - allocate a scatterlist with equally sized elements
  * @length: Length in bytes of the scatterlist. Must be at least one
- * @order: Second argument for alloc_pages()
+ * @order: Second argument for alloc_pages(). Each sgl element size will
+ *	   be (PAGE_SIZE*2^order) bytes
  * @chainable: Whether or not to allocate an extra element in the scatterlist
- *	for scatterlist chaining purposes
+ *	       for scatterlist chaining purposes
  * @gfp: Memory allocation flags
- * @nent_p: [out] Number of entries in the scatterlist that have pages
+ * @nent_p: [out] Number of entries in the scatterlist that have pages.
+ *		  Ignored if NULL is given.
  *
  * Returns: A pointer to an initialized scatterlist or %NULL upon failure.
  */

Quoted 24 lines · Douglas Gilbert

lib/scatterlist.c +7 -4

index a59778946404..4986545beef9 100644
+++ b/lib/scatterlist.c

@@ -554,13 +554,15 @@ EXPORT_SYMBOL(sg_alloc_table_from_pages);
  #ifdef CONFIG_SGL_ALLOC
 
  /**
- * sgl_alloc_order - allocate a scatterlist and its pages
+ * sgl_alloc_order - allocate a scatterlist with equally sized elements
   * @length: Length in bytes of the scatterlist. Must be at least one
- * @order: Second argument for alloc_pages()
+ * @order: Second argument for alloc_pages(). Each sgl element size will
+ *	   be (PAGE_SIZE*2^order) bytes
   * @chainable: Whether or not to allocate an extra element in the scatterlist
- *	for scatterlist chaining purposes
+ *	       for scatterlist chaining purposes
   * @gfp: Memory allocation flags
- * @nent_p: [out] Number of entries in the scatterlist that have pages
+ * @nent_p: [out] Number of entries in the scatterlist that have pages.
+ *		  Ignored if NULL is given.
   *
   * Returns: A pointer to an initialized scatterlist or %NULL upon failure.
   */

lib/scatterlist.c struct scatterlist *sgl_alloc_order(unsigned long long length, · line 583

Quoted 10 lines

lib/scatterlist.c +2 -2

@@ -574,8 +576,8 @@ struct scatterlist *sgl_alloc_order(unsigned long long length,
  	u32 elem_len;
 
  	nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
-	/* Check for integer overflow */
-	if (length > (nent << (PAGE_SHIFT + order)))
+	/* Integer overflow if:  length > nent*2^(PAGE_SHIFT+order) */
+	if (ilog2(length) > ilog2(nent) + PAGE_SHIFT + order)
  		return NULL;
  	nalloc = nent;
  	if (chainable) {

This is a little bit too tortured now, how about this:

	if (length >> (PAGE_SHIFT + order) >= UINT_MAX)
		return NULL;
	nent = length >> (PAGE_SHIFT + order);
	if (length & ((1ULL << (PAGE_SHIFT + order)) - 1))
		nent++;

	if (chainable) {
		if (check_add_overflow(nent, 1, &nalloc))
			return NULL;
	}
	else
		nalloc = nent;

Quoted 36 lines · Jason Gunthorpe

Quoted 23 lines · Douglas Gilbert

lib/scatterlist.c +7 -4

index a59778946404..4986545beef9 100644
+++ b/lib/scatterlist.c

@@ -554,13 +554,15 @@ EXPORT_SYMBOL(sg_alloc_table_from_pages);
  #ifdef CONFIG_SGL_ALLOC
  /**
- * sgl_alloc_order - allocate a scatterlist and its pages
+ * sgl_alloc_order - allocate a scatterlist with equally sized elements
   * @length: Length in bytes of the scatterlist. Must be at least one
- * @order: Second argument for alloc_pages()
+ * @order: Second argument for alloc_pages(). Each sgl element size will
+ *	   be (PAGE_SIZE*2^order) bytes
   * @chainable: Whether or not to allocate an extra element in the scatterlist
- *	for scatterlist chaining purposes
+ *	       for scatterlist chaining purposes
   * @gfp: Memory allocation flags
- * @nent_p: [out] Number of entries in the scatterlist that have pages
+ * @nent_p: [out] Number of entries in the scatterlist that have pages.
+ *		  Ignored if NULL is given.
   *
   * Returns: A pointer to an initialized scatterlist or %NULL upon failure.
   */

lib/scatterlist.c struct scatterlist *sgl_alloc_order(unsigned long long length, · line 582

Quoted 9 lines

lib/scatterlist.c +2 -2

@@ -574,8 +576,8 @@ struct scatterlist *sgl_alloc_order(unsigned long long length,
  	u32 elem_len;
  	nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
-	/* Check for integer overflow */
-	if (length > (nent << (PAGE_SHIFT + order)))
+	/* Integer overflow if:  length > nent*2^(PAGE_SHIFT+order) */
+	if (ilog2(length) > ilog2(nent) + PAGE_SHIFT + order)
  		return NULL;
  	nalloc = nent;
  	if (chainable) {

This is a little bit too tortured now, how about this:

Quoted 13 lines

	if (length >> (PAGE_SHIFT + order) >= UINT_MAX)
		return NULL;
	nent = length >> (PAGE_SHIFT + order);
	if (length & ((1ULL << (PAGE_SHIFT + order)) - 1))
		nent++;

	if (chainable) {
		if (check_add_overflow(nent, 1, &nalloc))
			return NULL;
	}
	else
		nalloc = nent;

And your proposal is less <<tortured>> ?

I'm looking at performance, not elegance and I'm betting that two ilog2() calls [which boil down to ffs()] are faster than two right-shift-by-n_s and one left-shift-by-n . Perhaps an extra comment could help my code by noting that mathematically:
/* if n > m for positive n and m then: log(n) > log(m) */

The existing sg_zero_buffer() function is a bit restrictive. For example protection information (PI) blocks are usually initialized to 0xff bytes. As its name suggests sgl_memset() is modelled on memset(). One difference is the type of the val argument which is u8 rather than int. Plus it returns the number of bytes (over)written.

Change implementation of sg_zero_buffer() to call this new function.

Reviewed-by Bodo Stroesser <[email protected]>

Signed-off-by Douglas Gilbert <[email protected]>

 include/linux/scatterlist.h |  3 ++
 lib/scatterlist.c           | 65 +++++++++++++++++++++++++------------
 2 files changed, 48 insertions(+), 20 deletions(-)

include/linux/scatterlist.h +4 -0

index 71be65f9ebb5..70d3f1f73df1 100644
+++ b/include/linux/scatterlist.h

@@ -333,6 +333,9 @@ bool sgl_compare_sgl_idx(struct scatterlist *x_sgl, unsigned int x_nents, off_t
 			 struct scatterlist *y_sgl, unsigned int y_nents, off_t y_skip,
 			 size_t n_bytes, size_t *miscompare_idx);
 
+size_t sgl_memset(struct scatterlist *sgl, unsigned int nents, off_t skip,
+		  u8 val, size_t n_bytes);
+
 /*
  * Maximum number of entries that will be allocated in one piece, if
  * a list larger than this is required then chaining will be utilized.

lib/scatterlist.c +1 -13

index 9332365e7eb6..f06614a880c8 100644
+++ b/lib/scatterlist.c

@@ -1038,26 +1038,7 @@ EXPORT_SYMBOL(sg_pcopy_to_buffer);
 size_t sg_zero_buffer(struct scatterlist *sgl, unsigned int nents,
 		       size_t buflen, off_t skip)
 {
-	unsigned int offset = 0;
-	struct sg_mapping_iter miter;
-	unsigned int sg_flags = SG_MITER_ATOMIC | SG_MITER_TO_SG;
-
-	sg_miter_start(&miter, sgl, nents, sg_flags);
-
-	if (!sg_miter_skip(&miter, skip))
-		return false;
-
-	while (offset < buflen && sg_miter_next(&miter)) {
-		unsigned int len;
-
-		len = min(miter.length, buflen - offset);

Quoted 52 lines · Douglas Gilbert

The existing sg_zero_buffer() function is a bit restrictive. For example protection information (PI) blocks are usually initialized to 0xff bytes. As its name suggests sgl_memset() is modelled on memset(). One difference is the type of the val argument which is u8 rather than int. Plus it returns the number of bytes (over)written.

Change implementation of sg_zero_buffer() to call this new function.

Reviewed-by Bodo Stroesser <[email protected]>

Signed-off-by Douglas Gilbert <[email protected]>

  include/linux/scatterlist.h |  3 ++
  lib/scatterlist.c           | 65 +++++++++++++++++++++++++------------
  2 files changed, 48 insertions(+), 20 deletions(-)

include/linux/scatterlist.h +4 -0

index 71be65f9ebb5..70d3f1f73df1 100644
+++ b/include/linux/scatterlist.h

@@ -333,6 +333,9 @@ bool sgl_compare_sgl_idx(struct scatterlist *x_sgl, unsigned int x_nents, off_t
  			 struct scatterlist *y_sgl, unsigned int y_nents, off_t y_skip,
  			 size_t n_bytes, size_t *miscompare_idx);
 
+size_t sgl_memset(struct scatterlist *sgl, unsigned int nents, off_t skip,
+		  u8 val, size_t n_bytes);
+
  /*
   * Maximum number of entries that will be allocated in one piece, if
   * a list larger than this is required then chaining will be utilized.

lib/scatterlist.c +1 -18

index 9332365e7eb6..f06614a880c8 100644
+++ b/lib/scatterlist.c

@@ -1038,26 +1038,7 @@ EXPORT_SYMBOL(sg_pcopy_to_buffer);
  size_t sg_zero_buffer(struct scatterlist *sgl, unsigned int nents,
  		       size_t buflen, off_t skip)
  {
-	unsigned int offset = 0;
-	struct sg_mapping_iter miter;
-	unsigned int sg_flags = SG_MITER_ATOMIC | SG_MITER_TO_SG;
-
-	sg_miter_start(&miter, sgl, nents, sg_flags);
-
-	if (!sg_miter_skip(&miter, skip))
-		return false;
-
-	while (offset < buflen && sg_miter_next(&miter)) {
-		unsigned int len;
-
-		len = min(miter.length, buflen - offset);
-		memset(miter.addr, 0, len);
-
-		offset += len;
-	}
-

lib/scatterlist.c EXPORT_SYMBOL(sg_pcopy_to_buffer); · line 1043

Quoted 5 lines

lib/scatterlist.c +1 -2

-	sg_miter_stop(&miter);
-	return offset;
+	return sgl_memset(sgl, nents, skip, 0, buflen);
  }
  EXPORT_SYMBOL(sg_zero_buffer);

May as well make this one liner a static inline in the header. Just rename this function to sgl_memset so the diff is clearer