Skip to contentSkip to conversation

scatterlist: add operations for scsi_debug

PATCH In review Douglas Gilbert 3 participants 10 messages Nov 12, 2022 – Nov 16, 2022

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

v2 cover scatterlist: add operations for scsi_debug

The scsi_debug driver is essentially a ramdisk dressed up as a SCSI host with one or more SCSI devices attached. Like all low level SCSI drivers, the scsi_debug driver receives and provides data to the SCSI mid-level (and the block layer) using scatterlists whose interface is found in include/linux/scatterlist.h .

After trying kmalloc() then vmalloc() based storage for the scsi_debug driver, it was found that certain SCSI commands can be optimized if instead one or more scatterlists is used as its backing store. The specific SCSI command that benefits the most is VERIFY(BYTCHK=1) whose NVMe equivalent is COMPARE. These commands have data-out buffers provided by an application that are compared by the storage device with the LBA and count (of blocks) given in the command. In this case the sgl_equal_sgl() function can be used instead of setting up a temporary buffer.

The implementation of the more common SCSI READ and WRITE commands are simplified by using the sgl_copy_sgl() function.

The first patch in this series removes an undocumented 4 GB limit in the existing sgl_alloc_order() function.

In the final patch of this series, the scsi_debug driver uses the new facilities in scatterlist to replace its vmalloc() backing store with a sgl_alloc_order() based store. Also several loops based on memcpy() and memcmp() are replaced by the new scatterlist copy and 'equal' functions.

Changes since v1 (sent to linux-scsi list on 20221023)
- in sgl_alloc_order() add check that order argument is less then MAX_ORDER; protects following call to round_up()
- in sdeb_sgl_cmp_buf() within scsi_debug.c remove call to sg_miter_stop() as suggested by reviewer

Douglas Gilbert (5):
sgl_alloc_order: remove 4 GiB limit
scatterlist: add sgl_copy_sgl() function
scatterlist: add sgl_equal_sgl() function
scatterlist: add sgl_memset()
scsi_debug: change store from vmalloc to sgl

 drivers/scsi/Kconfig        |   3 +-
 drivers/scsi/scsi_debug.c   | 442 ++++++++++++++++++++++++------------
 include/linux/scatterlist.h |  33 ++-
 lib/scatterlist.c           | 255 ++++++++++++++++++---
 4 files changed, 562 insertions(+), 171 deletions(-)
Signature · 1 line
2.37.2
#1 lore raw

PATCH v2 1/5 sgl_alloc_order: remove 4 GiB limit

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 right hand side of the expression in the condition is resolved as u32 so it can not exceed UINT32_MAX (4 GiB) which means 'length' can not exceed that value.

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() whose length type is unsigned long long should be limited to 4 GB.

Solutions to this issue were discussed by Jason Gunthorpe <[email protected]> and Bodo Stroesser <[email protected]>. This version is base on a linux-scsi post by Jason titled: "Re:
[PATCH v7 1/4] sgl_alloc_order: remove 4 GiB limit" dated 20220201.

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 .

Cc Jason Gunthorpe <[email protected]>
Cc Bodo Stroesser <[email protected]>
---
 include/linux/scatterlist.h |  1 +
 lib/scatterlist.c           | 23 ++++++++++++++---------
 2 files changed, 15 insertions(+), 9 deletions(-)
include/linux/scatterlist.h +1 -0
index 375a5e90d86a..0930755a756e 100644
@@ -426,6 +426,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 */
 
lib/scatterlist.c +14 -9
index c8c3d675845c..ee69d33d1228 100644
@@ -585,13 +585,16 @@ EXPORT_SYMBOL(sg_alloc_table_from_pages_segment);
 #ifdef CONFIG_SGL_ALLOC
 
 /**
- * sgl_alloc_order - allocate a scatterlist and its pages
+ * sgl_alloc_order - allocate a scatterlist with equally sized elements each
+ *		     of which has 2^@order continuous pages
  * @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. @order must not exceed 16.
  * @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 @nent_p is NULL.
  *
  * Returns: A pointer to an initialized scatterlist or %NULL upon failure.
  */
@@ -601,14 +604,16 @@ struct scatterlist *sgl_alloc_order(unsigned long long length,
 {
 	struct scatterlist *sgl, *sg;
 	struct page *page;
-	unsigned int nent, nalloc;
+	uint64_t nent;
+	unsigned int nalloc;
 	u32 elem_len;
 
+	if (WARN_ON_ONCE(order >= MAX_ORDER))
+		return NULL;
 	nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
-	/* Check for integer overflow */
-	if (length > (nent << (PAGE_SHIFT + order)))
+	if (nent > UINT_MAX)
 		return NULL;
-	nalloc = nent;
+	nalloc = (unsigned int)nent;
 	if (chainable) {
 		/* Check for integer overflow */
 		if (nalloc + 1 < nalloc)
@@ -636,7 +641,7 @@ struct scatterlist *sgl_alloc_order(unsigned long long length,
 	}
 	WARN_ONCE(length, "length = %lld\n", length);
 	if (nent_p)
-		*nent_p = nent;
+		*nent_p = (unsigned int)nent;
 	return sgl;
 }
 EXPORT_SYMBOL(sgl_alloc_order);
Signature · 1 line
2.37.2
#2 lore raw

Re: [PATCH v2 1/5] sgl_alloc_order: remove 4 GiB limit

Quoted 21 lines · Douglas Gilbert

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 right hand side of the expression in the condition is resolved as u32 so it can not exceed UINT32_MAX (4 GiB) which means 'length' can not exceed that value.

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() whose length type is unsigned long long should be limited to 4 GB.

Solutions to this issue were discussed by Jason Gunthorpe <[email protected]> and Bodo Stroesser <[email protected]>. This version is base on a linux-scsi post by Jason titled: "Re:
[PATCH v7 1/4] sgl_alloc_order: remove 4 GiB limit" dated 20220201.

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 .

Quoted 7 lines
Cc Jason Gunthorpe <[email protected]>
Cc Bodo Stroesser <[email protected]>
---
 include/linux/scatterlist.h |  1 +
 lib/scatterlist.c           | 23 ++++++++++++++---------
 2 files changed, 15 insertions(+), 9 deletions(-)

I still prefer the version I posted here:

https://lore.kernel.org/linux-scsi/[email protected]/

Jason

#3 lore raw

Re: [PATCH v2 1/5] sgl_alloc_order: remove 4 GiB limit

Quoted 30 lines · Jason Gunthorpe
Quoted 21 lines · Douglas Gilbert

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 right hand side of the expression in the condition is resolved as u32 so it can not exceed UINT32_MAX (4 GiB) which means 'length' can not exceed that value.

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() whose length type is unsigned long long should be limited to 4 GB.

Solutions to this issue were discussed by Jason Gunthorpe <[email protected]> and Bodo Stroesser <[email protected]>. This version is base on a linux-scsi post by Jason titled: "Re:
[PATCH v7 1/4] sgl_alloc_order: remove 4 GiB limit" dated 20220201.

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 .

Quoted 7 lines
Cc Jason Gunthorpe <[email protected]>
Cc Bodo Stroesser <[email protected]>
---
  include/linux/scatterlist.h |  1 +
  lib/scatterlist.c           | 23 ++++++++++++++---------
  2 files changed, 15 insertions(+), 9 deletions(-)
Quoted 3 lines

I still prefer the version I posted here:

https://lore.kernel.org/linux-scsi/[email protected]/

Three reasons that I don't:
1) making the first argument of type size_t may constrict the size that can be allocated on a 32 bit machine (faint recollection of extended/expanded memory on 8086). uint64_t would be better than unsigned long long but see point 3)
2) making the last (fifth) argument of type size_t is overkill on a 64 bit machine. IMO 32 bits is sufficient. The maximum unsigned int is 2^32 - 1 and with a typical PAGE_SIZE of 4096 bytes and order 0, that is roughly 2^44 bytes or about 16 TB. If part of the kernel did want 16 TB in a single allocation, I hope it would choose a larger value for order. So then the maximum single allocation would be 2^(44+MAX_ORDER-1) bytes. Can I stop now?
3) it changes the signature of an existing exported kernel function requiring changes in several call sites. Changing an output pointer type may require more than a one line change at the existing call sites. Due to the fact that this patch is removing an existing 4 GB limit, those call sites have zero need for this. If I was maintaining the driver containing those call sites, I would be a bit peeved. [That said, maintaining out-of-tree patchsets, while trying to get them accepted in the mainline, is a considerable pain due to the constant changes in the block layer API.]

Doug Gilbert

#4 lore raw

Re: [PATCH v2 1/5] sgl_alloc_order: remove 4 GiB limit

Quoted 33 lines · Douglas Gilbert
Quoted 32 lines · Jason Gunthorpe
Quoted 21 lines · Douglas Gilbert

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 right hand side of the expression in the condition is resolved as u32 so it can not exceed UINT32_MAX (4 GiB) which means 'length' can not exceed that value.

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() whose length type is unsigned long long should be limited to 4 GB.

Solutions to this issue were discussed by Jason Gunthorpe <[email protected]> and Bodo Stroesser <[email protected]>. This version is base on a linux-scsi post by Jason titled: "Re:
[PATCH v7 1/4] sgl_alloc_order: remove 4 GiB limit" dated 20220201.

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 .

Quoted 7 lines
Cc Jason Gunthorpe <[email protected]>
Cc Bodo Stroesser <[email protected]>
---
  include/linux/scatterlist.h |  1 +
  lib/scatterlist.c           | 23 ++++++++++++++---------
  2 files changed, 15 insertions(+), 9 deletions(-)

I still prefer the version I posted here:

Quoted 7 lines
Quoted 1 line

https://lore.kernel.org/linux-scsi/[email protected]/

Three reasons that I don't:
1) making the first argument of type size_t may constrict the size that can be allocated on a 32 bit machine (faint recollection of extended/expanded memory on 8086). uint64_t would be better than unsigned long long but see point 3)

32 bit machines can't kmap more than size_t - so this is not correct. We can't put sgl tables into highmem.

Quoted 2 lines

2) making the last (fifth) argument of type size_t is overkill on a 64 bit machine. IMO 32 bits is sufficient.

IIRC, I changed it to obviously avoid integer promotion/truncation issues. It is better to handle those with correct typing than introducing a bunch of frail checks. We don't need to worry about the extra 32 bits in something like this.

Quoted 2 lines

3) it changes the signature of an existing exported kernel function requiring changes in several call sites.

So fix them. It is why we have one git tree. You'll get sympathy if it is more than 5-10 :)

Quoted 5 lines

type may require more than a one line change at the existing call sites. Due to the fact that this patch is removing an existing 4 GB limit, those call sites have zero need for this. If I was maintaining the driver containing those call sites, I would be a bit peeved.

Uh, if someone is "peeved" they are not understanding how kernel APIs are expected to evolve, I think.

It should be two patches, one to correct the types in the function signature, and another to resolve the 4G problem.

Quoted 3 lines

[That said, maintaining out-of-tree patchsets, while
trying to get them accepted in the mainline, is a considerable pain due to the constant changes in the block layer API.]

Which is consistent with how the community views in-kernel APIs.

Jason

#5 lore raw

PATCH v2 2/5 scatterlist: add sgl_copy_sgl() function

In reply to Douglas Gilbert

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(+)
include/linux/scatterlist.h +4 -0
index 0930755a756e..cea1edd246cb 100644
@@ -445,6 +445,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.
lib/scatterlist.c +74 -0

77 lines not on this page · raw message

Signature · 1 line
2.37.2
#6 lore raw

Re: [PATCH v2 2/5] scatterlist: add sgl_copy_sgl() function

Quoted 2 lines · Douglas Gilbert

Both the SCSI and NVMe subsystems receive user data from the block layer in scatterlist_s

No, they don't. For one thing there is no 'scatterlist_s', and second no one receives it. Block drivers need to generate it using the blk_rq_map_sg helper.

Quoted 8 lines

(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.

No, the scatterlist is a bad data structure, but for now we have to use it for dma-mapping non-contigous pieces of memory. For everything else it absolutely should not be used, and we should not add helpers to facilitate that.

NAK for this and the other helpers.

#7 lore raw

PATCH v2 3/5 scatterlist: add sgl_equal_sgl() function

In reply to Douglas Gilbert

After enabling copies between scatter gather lists (sgl_s), another storage related operation is to compare two sgl_s for equality. This new function is designed to partially implement NVMe's Compare command and the SCSI VERIFY(BYTCHK=1) command. Like memcmp() this function begins scanning at the start (of each sgl) and returns false on the first miscompare and stops comparing.

The sgl_equal_sgl_idx() function additionally yields the index (i.e. byte position) of the first miscompare. The additional parameter, miscompare_idx, is a pointer. If it 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 *miscompare_idx. Knowing the location of the first miscompare is needed to implement properly the SCSI COMPARE AND WRITE command.

---
 include/linux/scatterlist.h |   8 +++
 lib/scatterlist.c           | 110 ++++++++++++++++++++++++++++++++++++
 2 files changed, 118 insertions(+)
include/linux/scatterlist.h +8 -0
index cea1edd246cb..e1552a3e9e13 100644
@@ -449,6 +449,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_equal_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_equal_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.
lib/scatterlist.c +110 -0

113 lines not on this page · raw message

Signature · 1 line
2.37.2
#8 lore raw

PATCH v2 4/5 scatterlist: add sgl_memset()

In reply to 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.

---
 include/linux/scatterlist.h | 20 +++++++++-
 lib/scatterlist.c           | 78 ++++++++++++++++++++-----------------
 2 files changed, 61 insertions(+), 37 deletions(-)
include/linux/scatterlist.h +18 -2
index e1552a3e9e13..dbcf0f6fd8d9 100644
@@ -442,8 +442,6 @@ size_t sg_pcopy_from_buffer(struct scatterlist *sgl, unsigned int nents,
 			    const void *buf, size_t buflen, off_t skip);
 size_t sg_pcopy_to_buffer(struct scatterlist *sgl, unsigned int nents,
 			  void *buf, size_t buflen, off_t skip);
-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,
@@ -457,6 +455,24 @@ bool sgl_equal_sgl_idx(struct scatterlist *x_sgl, unsigned int x_nents, off_t x_
 		       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);
+
+/**
+ * sg_zero_buffer - Zero-out a part of a SG list
+ * @sgl:		The SG list
+ * @nents:		Number of SG entries
+ * @buflen:		The number of bytes to zero out
+ * @skip:		Number of bytes to skip before zeroing
+ *
+ * Returns the number of bytes zeroed.
+ **/
+static inline size_t sg_zero_buffer(struct scatterlist *sgl, unsigned int nents,
+				    size_t buflen, off_t skip)
+{
+	return sgl_memset(sgl, nents, skip, 0, buflen);
+}
+
 /*
  * 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 +43 -35

87 lines not on this page · raw message

Signature · 1 line
2.37.2
#9 lore raw

PATCH v2 5/5 scsi_debug: change store from vmalloc to sgl

In reply to Douglas Gilbert

A long time ago this driver's store was allocated by kmalloc() or alloc_pages(). When this was switched to vmalloc() the author noticed slower ramdisk access times and more variability in repeated tests. So try going back with sgl_alloc_order() to get uniformly sized allocations in a sometimes large scatter gather _array_. That array is the basis of maintaining O(1) access to the store.

Using sgl_alloc_order() and friends requires CONFIG_SGL_ALLOC so add a 'select' to the Kconfig file.

Remove kcalloc() in resp_verify() as sgl_s can now be compared directly without forming an intermediate buffer. This is a performance win for the SCSI VERIFY command implementation.

Make the SCSI COMPARE AND WRITE command yield the offset of the first miscompared byte when the compare fails (as required by T10).

---
 drivers/scsi/Kconfig      |   3 +-
 drivers/scsi/scsi_debug.c | 442 ++++++++++++++++++++++++++------------
 2 files changed, 305 insertions(+), 140 deletions(-)
drivers/scsi/Kconfig +2 -1
index 03e71e3d5e5b..97edb4e17319 100644
@@ -1229,13 +1229,14 @@ config SCSI_DEBUG
 	tristate "SCSI debugging host and device simulator"
 	depends on SCSI
 	select CRC_T10DIF
+	select SGL_ALLOC
 	help
 	  This pseudo driver simulates one or more hosts (SCSI initiators),
 	  each with one or more targets, each with one or more logical units.
 	  Defaults to one of each, creating a small RAM disk device. Many
 	  parameters found in the /sys/bus/pseudo/drivers/scsi_debug
 	  directory can be tweaked at run time.
-	  See <http://sg.danny.cz/sg/sdebug26.html> for more information.
+	  See <https://sg.danny.cz/sg/scsi_debug.html> for more information.
 	  Mainly used for testing and best as a module. If unsure, say N.
 
 config SCSI_MESH
drivers/scsi/scsi_debug.c +303 -139

703 lines not on this page · raw message

Signature · 1 line
2.37.2