Re: [PATCH v5 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning

[Douglas Gilbert <dgilbert@interlog.com>]

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