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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-ID: <20180626113712.GB30877@mtr-leonro.mtl.com>
Date:   Tue, 26 Jun 2018 14:37:12 +0300
From:   Leon Romanovsky <leon@...nel.org>
To:     Rasmus Villemoes <linux@...musvillemoes.dk>
Cc:     Jason Gunthorpe <jgg@...lanox.com>,
        Doug Ledford <dledford@...hat.com>,
        Kees Cook <keescook@...omium.org>,
        RDMA mailing list <linux-rdma@...r.kernel.org>,
        Hadar Hen Zion <hadarh@...lanox.com>,
        Matan Barak <matanb@...lanox.com>,
        Michael J Ruhl <michael.j.ruhl@...el.com>,
        Noa Osherovich <noaos@...lanox.com>,
        Raed Salem <raeds@...lanox.com>,
        Yishai Hadas <yishaih@...lanox.com>,
        Saeed Mahameed <saeedm@...lanox.com>,
        linux-netdev <netdev@...r.kernel.org>,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH rdma-next 08/12] overflow.h: Add arithmetic shift helper

On Tue, Jun 26, 2018 at 10:07:07AM +0200, Rasmus Villemoes wrote:
> On 25 June 2018 at 19:11, Jason Gunthorpe <jgg@...lanox.com> 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

Download attachment "signature.asc" of type "application/pgp-signature" (802 bytes)