Re: [PATCH rdma-next 08/12] overflow.h: Add arithmetic shift helper

From: Leon Romanovsky
Date: Tue Jun 26 2018 - 07:37:21 EST


On Tue, Jun 26, 2018 at 10:07:07AM +0200, Rasmus Villemoes wrote:
> On 25 June 2018 at 19:11, Jason Gunthorpe <jgg@xxxxxxxxxxxx> wrote:
>
> > On Mon, Jun 25, 2018 at 11:26:05AM +0200, Rasmus Villemoes wrote:
> >
> > > check_shift_overflow(a, s, d) {
> > > unsigned _nbits = 8*sizeof(a);
> > > typeof(a) _a = (a);
> > > typeof(s) _s = (s);
> > > typeof(d) _d = (d);
> > >
> > > *_d = ((u64)(_a) << (_s & (_nbits-1)));
> > > _s >= _nbits || (_s > 0 && (_a >> (_nbits - _s -
> > > is_signed_type(a))) != 0);
> > > }
> >
> > Those types are not quite right.. What about this?
> >
> > check_shift_overflow(a, s, d) ({
> > unsigned int _nbits = 8*sizeof(d) - is_signed_type(d);
> > typeof(d) _a = a; // Shift is always performed on type 'd'
> > typeof(s) _s = s;
> > typeof(d) _d = d;
> >
> > *_d = (_a << (_s & (_nbits-1)));
> >
> > (((*_d) >> (_s & (_nbits-1)) != _a);
> > })
> >
>
> No, because, the check_*_overflow (and the __builtin_*_overflow cousins)
> functions must do their job without causing undefined behaviour, regardless
> of what crazy input values and types they are given. Also, the output must
> be completely defined for all inputs [1]. I omitted it for brevity, but I
> also wanted a and *d to have the same type, so there should also be one of
> those (void)(&_a == _d); statements. See the other check_*_overflow and the
> commit adding them. Without the (u64) cast, any signed (and negative) a
> would cause UB in your suggestion. Also, having _nbits be 31 when a (and/or
> *d) has type int, and then and'ing the shift by 30 doesn't make any sense;
> I have no idea what you're trying to do. I haven't tested the above, but I
> know from when I wrote the other ones that gcc is smart enough not to
> actually do the arithmetic in 64 bits when only <= 32 bit types are
> involved (i.e., gcc sees that the result is anyway implicitly truncated to
> 32 bits, so only bothers to compute the lower 32 bits).
>
> [1] For this one, it would probably be most consistent to say that the
> result is a*2^s computed in infinite-precision, then truncated to fit in d.
> So for too large s, that would just yield 0. But that becomes a bit
> annoying when s is negative; we don't want to start handling a negative
> left shift as a right shift. That's also why I said that one should sit
> down and think about the semantics one really wants, then implement that,
> and write tests. For a first implementation, it might be completely
> reasonable to simply say BUILD_BUG_ON(is_signed_type(a)), but that still
> leaves open what to put in *d when s is negative. But maybe another
> BUILD_BUG_ON(is_signed_type(s)) could handle that, though that's a bit
> annoying for integer literals.
>
> And can we use mathamatcial invertability to prove no overlow and
> > bound _a ? As above.
> >
>
> It's quite possible that the expression determining whether overflow
> occured can be written differently, possibly in terms of shifting back, but
> it definitely needs to return true when s is greater than nbits;
> check_shift_overflow(1U, 32, &d) must be true. And that expression also
> must not involve UB.

Rasmus,

RDMA doesn't really need specific size_t variant, but wants to prevent
shift overflows from users commands, so any true/false function/macro
will work for us.

https://patchwork.kernel.org/patch/10484055/
https://patchwork.kernel.org/patch/10484053/

Thanks

>
> Rasmus

Attachment: signature.asc
Description: PGP signature