scatterlist: add new capabilities

This patchset was sent to the linux-block and linux-scsi lists a few hours ago. If it is accepted that will probably be via the linux-block maintainer. It has potential users in the target sub-system and the scsi_debug driver. Other parts of the kernel that use <linux/scatterlist.h> may be interested which is why it is now being sent to the linux-kernel list.

Scatter-gather lists (sgl_s) are frequently used as data carriers in the block layer. For example the SCSI and NVMe subsystems interchange data with the block layer using sgl_s. The sgl API is declared in <linux/scatterlist.h>

The author has extended these transient sgl use cases to a store (i.e. a ramdisk) in the scsi_debug driver. Other new potential uses of sgl_s could be for the target subsystem. When this extra step is taken, the need to copy between sgl_s becomes apparent. The patchset adds sgl_copy_sgl() and two other sgl operations.

The existing sgl_alloc_order() function can be seen as a replacement for vmalloc() for large, long-term allocations. For what seems like no good reason, sgl_alloc_order() currently restricts its total allocation to less than or equal to 4 GiB. vmalloc() has no such restriction.

Changes since v3 [posted 20201019]:
- re-instate check on integer overflow of nent calculation in sgl_alloc_order(). Do it in such a way as to not limit the overall sgl size to 4 GiB
- introduce sgl_compare_sgl_idx() helper function that, if requested and if a miscompare is detected, will yield the byte index of the first miscompare.
- add Reviewed-by tags from Bodo Stroesser
- rebase on lk 5.10.0-rc2 [was on lk 5.9.0]

Changes since v2 [posted 20201018]:
- remove unneeded lines from sgl_memset() definition.
- change sg_zero_buffer() to call sgl_memset() as the former is a subset.

Changes since v1 [posted 20201016]:
- Bodo Stroesser pointed out a problem with the nesting of kmap_atomic() [called via sg_miter_next()] and kunmap_atomic() calls [called via sg_miter_stop()] and proposed a solution that simplifies the previous code.

- the new implementation of the three functions has shorter periods when pre-emption is disabled (but has more them). This should make operations on large sgl_s more pre-emption "friendly" with a relatively small performance hit.

- sgl_memset return type changed from void to size_t and is the number of bytes actually (over)written. That number is needed anyway internally so may as well return it as it may be useful to the caller.

This patchset is against lk 5.10.0-rc2

Douglas Gilbert (4):
sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
scatterlist: add sgl_copy_sgl() function
scatterlist: add sgl_compare_sgl() function
scatterlist: add sgl_memset()

 include/linux/scatterlist.h |  16 +++
 lib/scatterlist.c           | 244 +++++++++++++++++++++++++++++++++---
 2 files changed, 243 insertions(+), 17 deletions(-)

2.25.1

This patch fixes a check done by sgl_alloc_order() before it starts any allocations. The comment in the original said: "Check for integer overflow" but the check itself contained an integer overflow! The right hand side (rhs) of the expression in the condition is resolved as u32 so it could not exceed UINT32_MAX (4 GiB) which means 'length' could not exceed that value. If that was the intention then the comment above it could be dropped and the condition rewritten more clearly as:

     if (length > UINT32_MAX) <<failure path >>;

Get around the integer overflow problem in the rhs of the original check by taking ilog2() of both sides.

This function may be used to replace vmalloc(unsigned long) for a large allocation (e.g. a ramdisk). vmalloc has no limit at 4 GiB so it seems unreasonable that:
sgl_alloc_order(unsigned long long length, ....)
does. sgl_s made with sgl_alloc_order() have equally sized segments placed in a scatter gather array. That allows O(1) navigation around a big sgl using some simple integer arithmetic.

Revise some of this function's description to more accurately reflect what this function is doing.

An earlier patch fixed a memory leak in sg_alloc_order() due to the misuse of sgl_free(). Take the opportunity to put a one line comment above sgl_free()'s declaration warning that it is not suitable when order > 0 .

---
 include/linux/scatterlist.h |  1 +
 lib/scatterlist.c           | 14 ++++++++------
 2 files changed, 9 insertions(+), 6 deletions(-)

index 36c47e7e66a2..d9443ebd0a8e 100644
@@ -308,6 +308,7 @@ struct scatterlist *sgl_alloc(unsigned long long length, gfp_t gfp,
 			      unsigned int *nent_p);
 void sgl_free_n_order(struct scatterlist *sgl, int nents, int order);
 void sgl_free_order(struct scatterlist *sgl, int order);
+/* Only use sgl_free() when order is 0 */
 void sgl_free(struct scatterlist *sgl);
 #endif /* CONFIG_SGL_ALLOC */
 

index a59778946404..4986545beef9 100644
@@ -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.
  */

@@ -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) {

2.25.1

Both the SCSI and NVMe subsystems receive user data from the block layer in scatterlist_s (aka scatter gather lists (sgl) which are often arrays). If drivers in those subsystems represent storage (e.g. a ramdisk) or cache "hot" user data then they may also choose to use scatterlist_s. Currently there are no sgl to sgl operations in the kernel. Start with a sgl to sgl copy. Stops when the first of the number of requested bytes to copy, or the source sgl, or the destination sgl is exhausted. So the destination sgl will _not_ grow.

---
 include/linux/scatterlist.h |  4 ++
 lib/scatterlist.c           | 74 +++++++++++++++++++++++++++++++++++++
 2 files changed, 78 insertions(+)

index d9443ebd0a8e..f2922a34b140 100644
@@ -327,6 +327,10 @@ size_t sg_pcopy_to_buffer(struct scatterlist *sgl, unsigned int nents,
 size_t sg_zero_buffer(struct scatterlist *sgl, unsigned int nents,
 		       size_t buflen, off_t skip);
 
+size_t sgl_copy_sgl(struct scatterlist *d_sgl, unsigned int d_nents, off_t d_skip,
+		    struct scatterlist *s_sgl, unsigned int s_nents, off_t s_skip,
+		    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.

2.25.1

After enabling copies between scatter gather lists (sgl_s), another storage related operation is to compare two sgl_s. This new function is modelled on NVMe's Compare command and the SCSI VERIFY(BYTCHK=1) command. Like memcmp() this function returns false on the first miscompare and stops comparing.

A helper function called sgl_compare_sgl_idx() is added. It takes an additional parameter (miscompare_idx) which is a pointer. If that pointer is non-NULL and a miscompare is detected (i.e. the function returns false) then the byte index of the first miscompare is written to *miscomapre_idx. Knowing the location of the first miscompare is needed to implement the SCSI COMPARE AND WRITE command properly.

---
 include/linux/scatterlist.h |   8 +++
 lib/scatterlist.c           | 109 ++++++++++++++++++++++++++++++++++++
 2 files changed, 117 insertions(+)

index f2922a34b140..0f6d59bf66cb 100644
@@ -331,6 +331,14 @@ size_t sgl_copy_sgl(struct scatterlist *d_sgl, unsigned int d_nents, off_t d_ski
 		    struct scatterlist *s_sgl, unsigned int s_nents, off_t s_skip,
 		    size_t n_bytes);
 
+bool sgl_compare_sgl(struct scatterlist *x_sgl, unsigned int x_nents, off_t x_skip,
+		     struct scatterlist *y_sgl, unsigned int y_nents, off_t y_skip,
+		     size_t n_bytes);
+
+bool sgl_compare_sgl_idx(struct scatterlist *x_sgl, unsigned int x_nents, off_t x_skip,
+			 struct scatterlist *y_sgl, unsigned int y_nents, off_t y_skip,
+			 size_t n_bytes, size_t *miscompare_idx);
+
 /*
  * Maximum number of entries that will be allocated in one piece, if
  * a list larger than this is required then chaining will be utilized.

2.25.1

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.

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

index 0f6d59bf66cb..8e4c050e6237 100644
@@ -339,6 +339,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.

2.25.1