On Tue, Jun 26, 2018 at 10:07:07AM +0200, Rasmus Villemoes wrote:

On 25 June 2018 at 19:11, Jason Gunthorpe [off-list ref] wrote:

quoted

On Mon, Jun 25, 2018 at 11:26:05AM +0200, Rasmus Villemoes wrote:

quoted

   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

quoted

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