scatterlist: add new capabilities
Subsystems (5)
v6 cover scatterlist: add new capabilities
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(), sgl_compare_sgl() and sgl_memset().
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 v5 [posted 20201228]:
- incorporate review requests from Jason Gunthorpe
- replace integer overflow detection code in sgl_alloc_order() with a pre-condition statement
- rebase on lk 5.11.0-rc4
Changes since v4 [posted 20201105]:
- rebase on lk 5.10.0-rc2
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.11.0-rc4
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 | 33 ++++- lib/scatterlist.c | 253 +++++++++++++++++++++++++++++++----- 2 files changed, 253 insertions(+), 33 deletions(-)
Signature · 1 line
2.25.1
PATCH v6 1/4 sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
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 >>;
After several flawed attempts to detect overflow, take the fastest route by stating as a pre-condition that the 'order' function argument cannot exceed 16 (2^16 * 4k = 256 MiB).
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 | 21 ++++++++++----------- 2 files changed, 11 insertions(+), 11 deletions(-)
include/linux/scatterlist.h +1 -0
@@ -302,6 +302,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 +10 -11
@@ -554,13 +554,16 @@ 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 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 NULL is given. * * Returns: A pointer to an initialized scatterlist or %NULL upon failure. */
@@ -574,15 +577,11 @@ 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))) -return NULL ; - nalloc = nent;if (chainable) { -/* Check for integer overflow */ -if (nalloc +1 < nalloc) +if (check_add_overflow (nent,1U , &nalloc))return NULL ; - nalloc++; + }else { + nalloc = nent; } sgl =kmalloc_array (nalloc,sizeof (struct scatterlist ), gfp & ~GFP_DMA );
Signature · 1 line
2.25.1
Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
Quoted 3 lines · Douglas Gilbert
After several flawed attempts to detect overflow, take the fastest route by stating as a pre-condition that the 'order' function argument cannot exceed 16 (2^16 * 4k = 256 MiB).
That doesn't help, the point of the overflow check is similar to overflow checks in kcalloc: to prevent the routine from allocating less memory than the caller might assume.
For instance ipr_store_update_fw() uses request_firmware() (which is controlled by userspace) to drive the length argument to sgl_alloc_order(). If userpace gives too large a value this will corrupt kernel memory.
So this math:
nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
Needs to be checked, add a precondition to order does not help. I already proposed a straightforward algorithm you can use.
Jason
Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
Quoted 10 lines · Jason Gunthorpe
Quoted 3 lines · Douglas Gilbert
After several flawed attempts to detect overflow, take the fastest route by stating as a pre-condition that the 'order' function argument cannot exceed 16 (2^16 * 4k = 256 MiB).
That doesn't help, the point of the overflow check is similar to overflow checks in kcalloc: to prevent the routine from allocating less memory than the caller might assume.
Quoted 8 lines
For instance
ipr_store_update_fw()usesrequest_firmware()(which is controlled by userspace) to drive the length argument tosgl_alloc_order(). If userpace gives too large a value this will corrupt kernel memory.So this math:
nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
But that check itself overflows if order is too large (e.g. 65). A pre-condition says that the caller must know or check a value is sane, and if the user space can have a hand in the value passed the caller _must_ check pre-conditions IMO. A pre-condition also implies that the function's implementation will not have code to check the pre-condition.
My "log of both sides" proposal at least got around the overflowing left shift problem. And one reviewer, Bodo Stroesser, liked it.
Quoted 2 lines
Needs to be checked, add a precondition to order does not help. I already proposed a straightforward algorithm you can use.
It does help, it stops your proposed check from being flawed :-)
Giving a false sense of security seems more dangerous than a pre-condition statement IMO. Bart's original overflow check (in the mainline) limits length to 4GB (due to wrapping inside a 32 bit unsigned).
Also note there is another pre-condition statement in that function's definition, namely that length cannot be 0.
So perhaps you, Bart Van Assche and Bodo Stroesser, should compare notes and come up with a solution that you are _all_ happy with. The pre-condition works for me and is the fastest. The 'length' argument might be large, say > 1 GB [I use 1 GB in testing but did try 4GB and found the bug I'm trying to fix] but having individual elements greater than say 32 MB each does not seem very practical (and fails on the systems that I test with). In my testing the largest element size is 4 MB.
Doug Gilbert
Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
Quoted 16 lines · Douglas Gilbert
Quoted 15 lines · Jason Gunthorpe
Quoted 3 lines · Douglas Gilbert
After several flawed attempts to detect overflow, take the fastest route by stating as a pre-condition that the 'order' function argument cannot exceed 16 (2^16 * 4k = 256 MiB).
That doesn't help, the point of the overflow check is similar to overflow checks in kcalloc: to prevent the routine from allocating less memory than the caller might assume.
For instance
ipr_store_update_fw()usesrequest_firmware()(which is controlled by userspace) to drive the length argument tosgl_alloc_order(). If userpace gives too large a value this will corrupt kernel memory.
Quoted 5 lines
Quoted 3 lines
So this math:
nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);But that check itself overflows if order is too large (e.g. 65).
I don't reall care about order. It is always controlled by the kernel and it is fine to just require it be low enough to not overflow. length is the data under userspace control so math on it must be checked for overflow.
Quoted 2 lines
Also note there is another pre-condition statement in that function's definition, namely that length cannot be 0.
I don't see callers checking for that either, if it is true length 0 can't be allowed it should be blocked in the function
Jason
Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
Quoted 28 lines · Jason Gunthorpe
Quoted 16 lines · Douglas Gilbert
Quoted 15 lines · Jason Gunthorpe
Quoted 3 lines · Douglas Gilbert
After several flawed attempts to detect overflow, take the fastest route by stating as a pre-condition that the 'order' function argument cannot exceed 16 (2^16 * 4k = 256 MiB).
That doesn't help, the point of the overflow check is similar to overflow checks in kcalloc: to prevent the routine from allocating less memory than the caller might assume.
For instance
ipr_store_update_fw()usesrequest_firmware()(which is controlled by userspace) to drive the length argument tosgl_alloc_order(). If userpace gives too large a value this will corrupt kernel memory.Quoted 5 lines
Quoted 3 lines
So this math:
nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);But that check itself overflows if order is too large (e.g. 65).
I don't reall care about order. It is always controlled by the kernel and it is fine to just require it be low enough to not overflow. length is the data under userspace control so math on it must be checked for overflow.
Quoted 8 lines
Quoted 2 lines
Also note there is another pre-condition statement in that function's definition, namely that length cannot be 0.
I don't see callers checking for that either, if it is true length 0 can't be allowed it should be blocked in the function
Jason
A already said, I also think there should be a check for length or rather nent overflow.
I like the easy to understand check in your proposed code:
if (length >> (PAGE_SHIFT + order) >= UINT_MAX) return NULL;
But I don't understand, why you open-coded the nent calculation:
nent = length >> (PAGE_SHIFT + order); if (length & ((1ULL << (PAGE_SHIFT + order)) - 1)) nent++;
Wouldn't it be better to keep the original line instead:
nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
Or maybe even better:
nent = DIV_ROUND_UP(length, PAGE_SIZE << order);
I think, combining the above lines results in short and easily readable code:
u32 elem_len;
if (length >> (PAGE_SHIFT + order) >= UINT_MAX)
return NULL;
nent = DIV_ROUND_UP(length, PAGE_SIZE << order);
if (chainable) {
if (check_add_overflow(nent, 1, &nalloc))
return NULL;
}
else
nalloc = nent;Thank you,
Bodo
Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
Quoted 47 lines · Bodo Stroesser
Quoted 28 lines · Jason Gunthorpe
Quoted 16 lines · Douglas Gilbert
Quoted 15 lines · Jason Gunthorpe
Quoted 3 lines · Douglas Gilbert
After several flawed attempts to detect overflow, take the fastest route by stating as a pre-condition that the 'order' function argument cannot exceed 16 (2^16 * 4k = 256 MiB).
That doesn't help, the point of the overflow check is similar to overflow checks in kcalloc: to prevent the routine from allocating less memory than the caller might assume.
For instance
ipr_store_update_fw()usesrequest_firmware()(which is controlled by userspace) to drive the length argument tosgl_alloc_order(). If userpace gives too large a value this will corrupt kernel memory.Quoted 5 lines
Quoted 3 lines
So this math:
nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);But that check itself overflows if order is too large (e.g. 65).
I don't reall care about order. It is always controlled by the kernel and it is fine to just require it be low enough to not overflow. length is the data under userspace control so math on it must be checked for overflow.
Quoted 8 lines
Quoted 2 lines
Also note there is another pre-condition statement in that function's definition, namely that length cannot be 0.
I don't see callers checking for that either, if it is true length 0 can't be allowed it should be blocked in the function
Jason
A already said, I also think there should be a check for length or rather nent overflow.
I like the easy to understand check in your proposed code:
if (length >> (PAGE_SHIFT + order) >= UINT_MAX) return NULL;
Quoted 5 lines
But I don't understand, why you open-coded the nent calculation:
nent = length >> (PAGE_SHIFT + order); if (length & ((1ULL << (PAGE_SHIFT + order)) - 1)) nent++;
It is necessary to properly check for overflow, because the easy to understand check doesn't prove that round_up will work, only that >> results in something that fits in an int and that +1 won't overflow the int.
Quoted 3 lines
Wouldn't it be better to keep the original line instead:
nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
This can overflow inside the round_up
Jason
Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
Quoted 59 lines · Jason Gunthorpe
Quoted 47 lines · Bodo Stroesser
Quoted 28 lines · Jason Gunthorpe
Quoted 16 lines · Douglas Gilbert
Quoted 15 lines · Jason Gunthorpe
Quoted 3 lines · Douglas Gilbert
After several flawed attempts to detect overflow, take the fastest route by stating as a pre-condition that the 'order' function argument cannot exceed 16 (2^16 * 4k = 256 MiB).
That doesn't help, the point of the overflow check is similar to overflow checks in kcalloc: to prevent the routine from allocating less memory than the caller might assume.
For instance
ipr_store_update_fw()usesrequest_firmware()(which is controlled by userspace) to drive the length argument tosgl_alloc_order(). If userpace gives too large a value this will corrupt kernel memory.Quoted 5 lines
Quoted 3 lines
So this math:
nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);But that check itself overflows if order is too large (e.g. 65).
I don't reall care about order. It is always controlled by the kernel and it is fine to just require it be low enough to not overflow. length is the data under userspace control so math on it must be checked for overflow.
Quoted 8 lines
Quoted 2 lines
Also note there is another pre-condition statement in that function's definition, namely that length cannot be 0.
I don't see callers checking for that either, if it is true length 0 can't be allowed it should be blocked in the function
Jason
A already said, I also think there should be a check for length or rather nent overflow.
I like the easy to understand check in your proposed code:
if (length >> (PAGE_SHIFT + order) >= UINT_MAX) return NULL;Quoted 5 lines
But I don't understand, why you open-coded the nent calculation:
nent = length >> (PAGE_SHIFT + order); if (length & ((1ULL << (PAGE_SHIFT + order)) - 1)) nent++;It is necessary to properly check for overflow, because the easy to understand check doesn't prove that
round_upwill work, only that >> results in something that fits in an int and that +1 won't overflow the int.
Quoted 5 lines
Quoted 3 lines
Wouldn't it be better to keep the original line instead:
nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);This can overflow inside the
round_up
To protect against the "unsigned long long" length being too big why not pick a large power of two and if someone can justify a larger value, they can send a patch.
if (length > 64ULL * 1024 * 1024 * 1024) return NULL;
So 64 GiB or a similar calculation involving PAGE_SIZE. Compiler does the multiplication and at run time there is only a 64 bit comparison.
I tested 6 one GiB ramdisks on an 8 GiB machine, worked fine until firefox was started. Then came the OOM killer ...
Doug Gilbert
Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
Quoted 6 lines · Douglas Gilbert
To protect against the "unsigned long long" length being too big why not pick a large power of two and if someone can justify a larger value, they can send a patch.
if (length > 64ULL * 1024 * 1024 * 1024) return NULL;
That is not how we protect against arithemetic overflows in the kernel
Jason
Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
In reply to Jason GunthorpeQuoted 59 lines · Jason Gunthorpe
Quoted 47 lines · Bodo Stroesser
Quoted 28 lines · Jason Gunthorpe
Quoted 16 lines · Douglas Gilbert
Quoted 15 lines · Jason Gunthorpe
Quoted 3 lines · Douglas Gilbert
After several flawed attempts to detect overflow, take the fastest route by stating as a pre-condition that the 'order' function argument cannot exceed 16 (2^16 * 4k = 256 MiB).
That doesn't help, the point of the overflow check is similar to overflow checks in kcalloc: to prevent the routine from allocating less memory than the caller might assume.
For instance
ipr_store_update_fw()usesrequest_firmware()(which is controlled by userspace) to drive the length argument tosgl_alloc_order(). If userpace gives too large a value this will corrupt kernel memory.Quoted 5 lines
Quoted 3 lines
So this math:
nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);But that check itself overflows if order is too large (e.g. 65).
I don't reall care about order. It is always controlled by the kernel and it is fine to just require it be low enough to not overflow. length is the data under userspace control so math on it must be checked for overflow.
Quoted 8 lines
Quoted 2 lines
Also note there is another pre-condition statement in that function's definition, namely that length cannot be 0.
I don't see callers checking for that either, if it is true length 0 can't be allowed it should be blocked in the function
Jason
A already said, I also think there should be a check for length or rather nent overflow.
I like the easy to understand check in your proposed code:
if (length >> (PAGE_SHIFT + order) >= UINT_MAX) return NULL;Quoted 5 lines
But I don't understand, why you open-coded the nent calculation:
nent = length >> (PAGE_SHIFT + order); if (length & ((1ULL << (PAGE_SHIFT + order)) - 1)) nent++;It is necessary to properly check for overflow, because the easy to understand check doesn't prove that
round_upwill work, only that >> results in something that fits in an int and that +1 won't overflow the int.
Quoted 5 lines
Quoted 3 lines
Wouldn't it be better to keep the original line instead:
nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);This can overflow inside the
round_up
I had a second look into math.h, but I don't find any reason why round_up could overflow. Can you give a hint please?
Regarding the overflow checks: would it be a good idea to not check length >> (PAGE_SHIFT + order) in the beginning, but check nalloc immediately before the kmalloc_array() as the only overrun check:
if ((unsigned long long)nalloc << (PAGE_SHIFT + order) < length) return NULL;
-Bodo
Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
Quoted 3 lines · Bodo Stroesser
I had a second look into
math.h, but I don't find any reason whyround_upcould overflow. Can you give a hint please?
#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1)
^^^^^That +1 can overflow
It looks like it would not be so bad to implement some check_round_up_overflow() if people prefer
Jason
Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
Quoted 9 lines · Jason Gunthorpe
Quoted 3 lines · Bodo Stroesser
I had a second look into
math.h, but I don't find any reason whyround_upcould overflow. Can you give a hint please?#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1) ^^^^^That +1 can overflow
But that would be a unsigned long long overflow. I considered this to not be relevant.
Quoted 6 lines
It looks like it would not be so bad to implement some
check_round_up_overflow()if people preferJason
Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
Quoted 6 lines · Bodo Stroesser
Quoted 5 lines · Jason Gunthorpe
Quoted 3 lines · Bodo Stroesser
I had a second look into
math.h, but I don't find any reason whyround_upcould overflow. Can you give a hint please?
Quoted 7 lines
Quoted 4 lines
#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1) ^^^^^That +1 can overflow
But that would be a unsigned long long overflow. I considered this to not be relevant.
Why not? It still makes nents 0 and still causes a bad bug
Jason
Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
Quoted 10 lines · Jason Gunthorpe
Quoted 9 lines · Bodo Stroesser
Quoted 8 lines · Jason Gunthorpe
Quoted 3 lines · Bodo Stroesser
I had a second look into
math.h, but I don't find any reason whyround_upcould overflow. Can you give a hint please?#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1) ^^^^^
Quoted 7 lines
Quoted 4 lines
Quoted 1 line
That +1 can overflow
But that would be a unsigned long long overflow. I considered this to not be relevant.
Why not? It still makes nents 0 and still causes a bad bug
Generally spoken, you of course are right.
OTOH, if someone tries to allocate such big sgls, then we will run into trouble during memory allocation even without overrun.
Anyway, if we first calculate nent and nalloc and then check with
if ((unsigned long long)nalloc << (PAGE_SHIFT + order) < length) return NULL;
I think we would have checked against all kind of overrun in a single step. Or am I missing something?
Bodo
Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning
In reply to Douglas GilbertQuoted 27 lines · Douglas Gilbert
Quoted 10 lines · Jason Gunthorpe
Quoted 3 lines · Douglas Gilbert
After several flawed attempts to detect overflow, take the fastest route by stating as a pre-condition that the 'order' function argument cannot exceed 16 (2^16 * 4k = 256 MiB).
That doesn't help, the point of the overflow check is similar to overflow checks in kcalloc: to prevent the routine from allocating less memory than the caller might assume.
Quoted 8 lines
For instance
ipr_store_update_fw()usesrequest_firmware()(which is controlled by userspace) to drive the length argument tosgl_alloc_order(). If userpace gives too large a value this will corrupt kernel memory.So this math:
nent =
round_up(length, PAGE_SIZE << order)>> (PAGE_SHIFT+ order);But that check itself overflows if order is too large (e.g. 65). A pre-condition says that the caller must know or check a value is sane, and if the user space can have a hand in the value passed the caller _must_ check pre-conditions IMO. A pre-condition also implies that the function's implementation will not have code to check the pre-condition.
Quoted 2 lines
My "log of both sides" proposal at least got around the overflowing left shift problem. And one reviewer, Bodo Stroesser, liked it.
I added my Reviewed-by after you added a working check of nent overflow. I did not oppose to the usage of ilog() there. But now I think Jason is right that indeed ilog usage is a bit 'indirect'.
Anyway I still think, there should be a check for nent overflow.
Quoted 26 lines
Quoted 3 lines
Needs to be checked, add a precondition to order does not help. I already proposed a straightforward algorithm you can use.
It does help, it stops your proposed check from being flawed :-)
Giving a false sense of security seems more dangerous than a pre-condition statement IMO. Bart's original overflow check (in the mainline) limits length to 4GB (due to wrapping inside a 32 bit unsigned).
Also note there is another pre-condition statement in that function's definition, namely that length cannot be 0.
So perhaps you, Bart Van Assche and Bodo Stroesser, should compare notes and come up with a solution that you are _all_ happy with. The pre-condition works for me and is the fastest. The 'length' argument might be large, say > 1 GB [I use 1 GB in testing but did try 4GB and found the bug I'm trying to fix] but having individual elements greater than say 32 MB each does not seem very practical (and fails on the systems that I test with). In my testing the largest element size is 4 MB.
Doug Gilbert
PATCH v6 2/4 scatterlist: add sgl_copy_sgl() function
In reply to Douglas GilbertBoth 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
@@ -321,6 +321,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.25.1
PATCH v6 3/4 scatterlist: add sgl_compare_sgl() function
In reply to Douglas GilbertAfter 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(+)
include/linux/scatterlist.h +8 -0
@@ -325,6 +325,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.
lib/scatterlist.c +109 -0
112 lines not on this page · raw message
Signature · 1 line
2.25.1
Re: [PATCH v6 3/4] scatterlist: add sgl_compare_sgl() function
Quoted 25 lines · Douglas Gilbert
After enabling copies between scatter gather lists (
sgl_s), another storage related operation is to compare twosgl_s. This new function is modelled on NVMe's Compare command and the SCSI VERIFY(BYTCHK=1) command. Likememcmp()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.Reviewed-by Bodo Stroesser <[email protected]>Signed-off-by Douglas Gilbert <[email protected]>--- include/linux/scatterlist.h | 8 +++ lib/scatterlist.c | 109 ++++++++++++++++++++++++++++++++++++ 2 files changed, 117 insertions(+)include/linux/scatterlist.h +0
-0
include/linux/scatterlist.h size_t sgl_copy_sgl(struct scatterlist *d_sgl, unsigned int d_nents, off_t d_ski · line 334
Quoted 10 lines
include/linux/scatterlist.h +7
-0@@ -325,6 +325,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);
This patch looks good and works fine as a replacement for compare_and_write_do_cmp(). One minor suggestion would be to name it sgl_equal() or similar, to perhaps better reflect the bool return and avoid memcmp() confusion. Either way:
Cheers, David
Re: [PATCH v6 3/4] scatterlist: add sgl_compare_sgl() function
Quoted 43 lines · David Disseldorp
Quoted 25 lines · Douglas Gilbert
After enabling copies between scatter gather lists (
sgl_s), another storage related operation is to compare twosgl_s. This new function is modelled on NVMe's Compare command and the SCSI VERIFY(BYTCHK=1) command. Likememcmp()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.Reviewed-by Bodo Stroesser <[email protected]>Signed-off-by Douglas Gilbert <[email protected]>--- include/linux/scatterlist.h | 8 +++ lib/scatterlist.c | 109 ++++++++++++++++++++++++++++++++++++ 2 files changed, 117 insertions(+)include/linux/scatterlist.h +0
-0include/linux/scatterlist.h size_t sgl_copy_sgl(struct scatterlist *d_sgl, unsigned int d_nents, off_t d_ski · line 334
Quoted 10 lines
include/linux/scatterlist.h +7
-0@@ -325,6 +325,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);This patch looks good and works fine as a replacement for
compare_and_write_do_cmp(). One minor suggestion would be to name itsgl_equal()or similar, to perhaps better reflect the bool return and avoidmemcmp()confusion. Either way:
Quoted 1 line
Reviewed-by David Disseldorp <[email protected]>
Thanks. NVMe calls the command that does this Compare and SCSI uses COMPARE AND WRITE (and VERIFY(BYTCHK=1) ) but "equal" is fine with me. There will be another patchset version (at least) so there is time to change.
Do you want:
- sgl_equal(...), or
- sgl_equal_sgl(...) ?
Doug Gilbert
Re: [PATCH v6 3/4] scatterlist: add sgl_compare_sgl() function
Quoted 15 lines · Douglas Gilbert
Quoted 13 lines
include/linux/scatterlist.h size_t sgl_copy_sgl(struct scatterlist *d_sgl, unsigned int d_nents, off_t d_ski · line 334
Quoted 7 lines
include/linux/scatterlist.h +7
-0+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);This patch looks good and works fine as a replacement for
compare_and_write_do_cmp(). One minor suggestion would be to name itsgl_equal()or similar, to perhaps better reflect the bool return and avoidmemcmp()confusion. Either way:Quoted 1 line
Reviewed-by David Disseldorp <[email protected]>
Quoted 8 lines
Thanks. NVMe calls the command that does this Compare and SCSI uses COMPARE AND WRITE (and VERIFY(BYTCHK=1) ) but "equal" is fine with me. There will be another patchset version (at least) so there is time to change.
Do you want:
-sgl_equal(...), or
-sgl_equal_sgl(...)?
I'd probably prefer the former as it's shorter, but I don't feel strongly about it. The latter would make sense if you expect sgl compare helpers for other buffer types.
Cheers, David
PATCH v6 4/4 scatterlist: add sgl_memset()
In reply to Douglas GilbertThe 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 | 79 +++++++++++++++++++++---------------- 2 files changed, 62 insertions(+), 37 deletions(-)
include/linux/scatterlist.h +18 -2
@@ -318,8 +318,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,
@@ -333,6 +331,24 @@ 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); + +/** +* 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 +44 -35
88 lines not on this page · raw message
Signature · 1 line
2.25.1