Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Date:   Mon, 11 Jan 2021 10:43:06 -0400
From:   Jason Gunthorpe <jgg@ziepe.ca>
To:     Douglas Gilbert <dgilbert@interlog.com>
Cc:     linux-scsi@vger.kernel.org, linux-block@vger.kernel.org,
        target-devel@vger.kernel.org, linux-rdma@vger.kernel.org,
        linux-kernel@vger.kernel.org, martin.petersen@oracle.com,
        jejb@linux.vnet.ibm.com, bostroesser@gmail.com, bvanassche@acm.org,
        ddiss@suse.de
Subject: Re: [PATCH v5 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free()
 warning
Message-ID: <20210111144306.GK504133@ziepe.ca>
References: <20201228234955.190858-1-dgilbert@interlog.com>
 <20201228234955.190858-2-dgilbert@interlog.com>
 <20210107174410.GB504133@ziepe.ca>
 <76827f07-9484-d2c6-346b-0bdccfdf4a7a@interlog.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <76827f07-9484-d2c6-346b-0bdccfdf4a7a@interlog.com>
Precedence: bulk

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