On Sat, Jan 09, 2021 at 05:58:50PM -0500, Douglas Gilbert wrote:

On 2021-01-07 12:44 p.m., Jason Gunthorpe wrote:

quoted

On Mon, Dec 28, 2020 at 06:49:52PM -0500, Douglas Gilbert wrote:

quoted

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