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 .
Reviewed-by: Bodo Stroesser <[email protected]>
Signed-off-by: Douglas Gilbert <[email protected]>
---
include/linux/scatterlist.h | 1 +
lib/scatterlist.c | 14 ++++++++------
2 files changed, 9 insertions(+), 6 deletions(-)
diff --git a/include/linux/scatterlist.h b/include/linux/scatterlist.h
index 6f70572b2938..8adff41f7cfa 100644
--- a/include/linux/scatterlist.h
+++ b/include/linux/scatterlist.h
@@ -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 */
diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index a59778946404..4986545beef9 100644
--- a/lib/scatterlist.c
+++ 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.
*/
@@ -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
On Mon, Dec 28, 2020 at 06:49:52PM -0500, Douglas Gilbert wrote:
> diff --git a/lib/scatterlist.c b/lib/scatterlist.c
> 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.
> */
> @@ -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;
Jason
On 2021-01-07 12:44 p.m., Jason Gunthorpe wrote:
> On Mon, Dec 28, 2020 at 06:49:52PM -0500, Douglas Gilbert wrote:
>> diff --git a/lib/scatterlist.c b/lib/scatterlist.c
>> 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.
>> */
>> @@ -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;
>
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) */
My original preference was to drop the check all together but Bart
Van Assche (who wrote that function) wanted me to keep it. Any
function that takes 'order' (i.e. an exponent) can blow up given
a silly value.
The chainable check_add_overflow() call is new and an improvement.
Doug Gilbert
On Sat, Jan 09, 2021 at 05:58:50PM -0500, Douglas Gilbert wrote:
> On 2021-01-07 12:44 p.m., Jason Gunthorpe wrote:
> > On Mon, Dec 28, 2020 at 06:49:52PM -0500, Douglas Gilbert wrote:
> > > diff --git a/lib/scatterlist.c b/lib/scatterlist.c
> > > 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.
> > > */
> > > @@ -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;
> >
>
> And your proposal is less <<tortured>> ?
Yes, obviously checking something fits in a variable is less tortured
than checking the result of math is correct.
> 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) */
One instruction difference seems completely irrelavent here.
If you care about micro-optimizing this then please add a
check_shr_overflow() just like we have for check_shl_overflow() that
has all the right tricks.
Probably:
input_type x = arg >> shift;
if (x != (output_type)x)
fail
return (output_type)x
Is fastest.
Jason