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

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

[Leon Romanovsky]

From: Leon Romanovsky <leonro@mellanox.com>

Add shift_overflow() helper to help driver authors to ensure that
shift operand doesn't cause to overflow, which is very common pattern
for RDMA drivers.

Signed-off-by: Leon Romanovsky <leonro@mellanox.com>
---
 include/linux/overflow.h | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

diff --git a/include/linux/overflow.h b/include/linux/overflow.h
index 8712ff70995f..2a3395248e94 100644
--- a/include/linux/overflow.h
+++ b/include/linux/overflow.h
@@ -202,6 +202,29 @@

 #endif /* COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW */

+/**
+ * shift_overflow() - Peform shift operation with overflow check
+ * @a: value to be shifted
+ * @b: shift operand
+ *
+ * Checks if a << b will overflow
+ *
+ * Returns: result of shift for no overflow or SIZE_MAX for overflow
+ */
+static inline __must_check size_t shift_overflow(size_t a, size_t b)
+{
+	size_t c, res;
+
+	if (b >= sizeof(size_t) * BITS_PER_BYTE)
+		return SIZE_MAX;
+
+	c = (size_t)1 << b;
+	if (check_mul_overflow(a, c, &res))
+		return SIZE_MAX;
+
+	return res;
+}
+
 /**
  * array_size() - Calculate size of 2-dimensional array.
  *
--
2.14.4

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

[Jason Gunthorpe]

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);
    })

And can we use mathamatcial invertability to prove no overlow and
bound _a ? As above.

Jason

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

[Leon Romanovsky]

[-- Attachment #1: Type: text/plain, Size: 1413 bytes --]

On Mon, Jun 25, 2018 at 11:11:57AM -0600, Jason Gunthorpe 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);
>     })
>
> And can we use mathamatcial invertability to prove no overlow and
> bound _a ? As above.

Rasmus and Jason,

Thanks for the feedback.
The reason why I introduced function, because wanted to reuse
check_mul_overflow macro, but for any reasons which I don't remember
now, I had hard time to fix compilation errors.

Anyway, I'll resubmit.

Thanks


>
> Jason
> --
> To unsubscribe from this list: send the line "unsubscribe linux-rdma" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

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

[Leon Romanovsky]

[-- Attachment #1: Type: text/plain, Size: 3492 bytes --]

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

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

[Jason Gunthorpe]

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

Okay, I see you are concerned about a UB during shifting signed
values. I didn't consider that..

>    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);

Humm. No, that doesn't match the use case. Typically this would take
an ABI constant like a u32 and shift it into a size_t for use with an
allocator. So demanding a and d have equal types is not good, and
requiring user casting is not good as the casting could be truncating.

>    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.

When thinking about signed cases.. The explicit u64 cast, and
implict promotion to typeof(d), produce something counter intuitive,
eg:

  (u64)(s32)-1 == 0xffffffffffffffff

Which would result in a shift oucome that is not what anyone would
expect, IMHO... So the first version isn't what I'd expect either..

>    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.

Yes, it is not helpful to avoid UB when a is signed..

>    [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.

I think this does not match the usual use cases, this should strictly
be an unsigned shift. The output is guarenteed to always be positive
or overflow is signaled.

Signed types are alllowed, but negative values are not.

What about more like this?

          check_shift_overflow(a, s, d) ({
	      // Shift is always performed on the machine's largest unsigned
              u64 _a = a;
	      typeof(s) _s = s;
              typeof(d) _d = d;

	      // Make s safe against UB
	      unsigned int _to_shift = _s >= 0 && _s < 8*sizeof(*d) : _s ? 0;

              *_d = (_a << _to_shift);

	       // s is malformed
              (_to_shift != _s ||
	       // d is a signed type and became negative
	       *_d < 0 ||
	       // a is a signed type and was negative
	       _a < 0 ||
	       // Not invertable means a was truncated during shifting
	       (*_d >> _to_shift) != a))
          })

I'm not seeing a UB with this?

Jason

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

[Leon Romanovsky]

[-- Attachment #1: Type: text/plain, Size: 939 bytes --]

On Wed, Jun 27, 2018 at 11:36:03AM +0200, Rasmus Villemoes wrote:
> On 26 June 2018 at 19:54, Jason Gunthorpe <jgg@mellanox.com> wrote:
>
> > On Tue, Jun 26, 2018 at 10:07:07AM +0200, Rasmus Villemoes wrote:
> > >    On 25 June 2018 at 19:11, Jason Gunthorpe <[1]jgg@mellanox.com>
> > wrote:
> > >
> >
> > When thinking about signed cases.. The explicit u64 cast, and
> > implict promotion to typeof(d), produce something counter intuitive,
> > eg:
> >
> >   (u64)(s32)-1 == 0xffffffffffffffff
> >
> > Which would result in a shift oucome that is not what anyone would
> > expect, IMHO... So the first version isn't what I'd expect either..
> >
>
> Wouldn't check_shift_overflow(-1, 4, &someint) just put -16 in someint and
> report no overflow? That's what I'd expect, if negative values are to be
> supported at all.

Most if not all the times we don't do shifts on negative values, so I
don't think that we should support them.

Thanks

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

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

[Jason Gunthorpe]

On Wed, Jun 27, 2018 at 11:36:03AM +0200, Rasmus Villemoes wrote:
>    OK. The requirement of everything having the same type for the
>    check_*_overflow when gccs builtins are not available was mostly a
>    consequence of my inability to implement completely type-generic
>    versions (but also to enforce some sanity, so people don't do
>    check_add_overflow( s8, size_t, int*)). There's no gcc builtin for
>    shift, but if it's relatively simple to one allowing a and *d to have
>    different types, then why not. It's of course particularly convenient
>    to allow a bare "1" (i.e. int) as a while having *d have some random
>    type.

Yes

>    Wouldn't check_shift_overflow(-1, 4, &someint) just put -16 in someint
>    and report no overflow? That's what I'd expect, if negative values are
>    to be supported at all.

I would say that is not a desired outcome, bitshift is defined on
bits, if the caller wanted something defined as signed multiply they
should use multiply.

IMHO, nobody writes 'a << b' expecting sign preservation..

>    Well, the types you can check at compile-time, the values not, so you
>    still have to define the result, i.e. contents of *d, for negative
>    values (even if we decide that "overflow" should always be signalled in
>    that case).

Why do a need to define a 'result' beyond whatever the not-undefined
behavior shift expression produces?

>      What about more like this?
>                check_shift_overflow(a, s, d) ({
>                    // Shift is always performed on the machine's largest
>      unsigned
>                    u64 _a = a;
>                    typeof(s) _s = s;
>                    typeof(d) _d = d;
>                    // Make s safe against UB
>                    unsigned int _to_shift = _s >= 0 && _s < 8*sizeof(*d) : _s ? 0;
>                    *_d = (_a << _to_shift);
>                     // s is malformed
>                    (_to_shift != _s ||
>                     // d is a signed type and became negative
>                     *_d < 0 ||
>                     // a is a signed type and was negative
>                     _a < 0 ||
>                     // Not invertable means a was truncated during
>      shifting
>                     (*_d >> _to_shift) != a))
>                })
>      I'm not seeing a UB with this?
> 
>    Something like that might work, but you're not there yet. In
>    particular, your test for whether a is negative is thwarted by using
>    u64 for _a and testing _a < 0...

Oops, yes that was intended to be 'a', and of course we need to
capture it..

Leon? Seems like agreement, Can you work with this version?

#include <stdint.h>
#include <stdbool.h>
#include <assert.h>

#define u64 uint64_t

/*
 * Compute *d = (a << s)
 *
 * Returns true if '*d' cannot hold the result or 'a << s' doesn't make sense.
 * - 'a << s' causes bits to be lost when stored in d
 * - 's' is garbage (eg negative) or so large that a << s is guarenteed to be 0
 * - 'a' is negative
 * - 'a << s' sets the sign bit, if any, in '*d'
 * *d is not defined if false is returned.
 */
#define check_shift_overflow(a, s, d)                                          \
	({                                                                     \
		typeof(a) _a = a;                                              \
		typeof(s) _s = s;                                              \
		typeof(d) _d = d;                                              \
		u64 _a_full = _a;                                              \
		unsigned int _to_shift =                                       \
			_s >= 0 && _s < 8 * sizeof(*d) ? _s : 0;               \
                                                                               \
		*_d = (_a_full << _to_shift);                                  \
                                                                               \
		(_to_shift != _s || *_d < 0 || _a < 0 ||                       \
		 (*_d >> _to_shift) != a);                                     \
	})

int main(int argc, const char *argv[])
{
	int32_t s32;
	uint32_t u32;

	assert(check_shift_overflow(1, 0, &s32) == false && s32 == (1 << 0));
	assert(check_shift_overflow(1, 1, &s32) == false && s32 == (1 << 1));
	assert(check_shift_overflow(1, 30, &s32) == false && s32 == (1 << 30));
	assert(check_shift_overflow(1, 31, &s32) == true);
	assert(check_shift_overflow(1, 32, &s32) == true);
	assert(check_shift_overflow(-1, 1, &s32) == true);
	assert(check_shift_overflow(-1, 0, &s32) == true);

	assert(check_shift_overflow(1, 0, &u32) == false && u32 == (1 << 0));
	assert(check_shift_overflow(1, 1, &u32) == false && u32 == (1 << 1));
	assert(check_shift_overflow(1, 30, &u32) == false && u32 == (1 << 30));
	assert(check_shift_overflow(1, 31, &u32) == false && u32 == (1UL << 31));
	assert(check_shift_overflow(1, 32, &u32) == true);
	assert(check_shift_overflow(-1, 1, &u32) == true);
	assert(check_shift_overflow(-1, 0, &u32) == true);

	assert(check_shift_overflow(0xFFFFFFFF, 0, &u32) == false && u32 == (0xFFFFFFFFUL << 0));
	assert(check_shift_overflow(0xFFFFFFFF, 1, &u32) == true);
	assert(check_shift_overflow(0xFFFFFFFF, 0, &s32) == true);
	assert(check_shift_overflow(0xFFFFFFFF, 1, &s32) == true);
}

Thanks,
Jason

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

[Leon Romanovsky]

On Wed, Jun 27, 2018 at 12:10:12PM -0600, Jason Gunthorpe wrote:
> On Wed, Jun 27, 2018 at 11:36:03AM +0200, Rasmus Villemoes wrote:
> >    OK. The requirement of everything having the same type for the
> >    check_*_overflow when gccs builtins are not available was mostly a
> >    consequence of my inability to implement completely type-generic
> >    versions (but also to enforce some sanity, so people don't do
> >    check_add_overflow( s8, size_t, int*)). There's no gcc builtin for
> >    shift, but if it's relatively simple to one allowing a and *d to have
> >    different types, then why not. It's of course particularly convenient
> >    to allow a bare "1" (i.e. int) as a while having *d have some random
> >    type.
>
> Yes
>
> >    Wouldn't check_shift_overflow(-1, 4, &someint) just put -16 in someint
> >    and report no overflow? That's what I'd expect, if negative values are
> >    to be supported at all.
>
> I would say that is not a desired outcome, bitshift is defined on
> bits, if the caller wanted something defined as signed multiply they
> should use multiply.
>
> IMHO, nobody writes 'a << b' expecting sign preservation..
>
> >    Well, the types you can check at compile-time, the values not, so you
> >    still have to define the result, i.e. contents of *d, for negative
> >    values (even if we decide that "overflow" should always be signalled in
> >    that case).
>
> Why do a need to define a 'result' beyond whatever the not-undefined
> behavior shift expression produces?
>
> >      What about more like this?
> >                check_shift_overflow(a, s, d) ({
> >                    // Shift is always performed on the machine's largest
> >      unsigned
> >                    u64 _a = a;
> >                    typeof(s) _s = s;
> >                    typeof(d) _d = d;
> >                    // Make s safe against UB
> >                    unsigned int _to_shift = _s >= 0 && _s < 8*sizeof(*d) : _s ? 0;
> >                    *_d = (_a << _to_shift);
> >                     // s is malformed
> >                    (_to_shift != _s ||
> >                     // d is a signed type and became negative
> >                     *_d < 0 ||
> >                     // a is a signed type and was negative
> >                     _a < 0 ||
> >                     // Not invertable means a was truncated during
> >      shifting
> >                     (*_d >> _to_shift) != a))
> >                })
> >      I'm not seeing a UB with this?
> >
> >    Something like that might work, but you're not there yet. In
> >    particular, your test for whether a is negative is thwarted by using
> >    u64 for _a and testing _a < 0...
>
> Oops, yes that was intended to be 'a', and of course we need to
> capture it..
>
> Leon? Seems like agreement, Can you work with this version?

Yes, sure, I waited for an agreement.

>
> #include <stdint.h>
> #include <stdbool.h>
> #include <assert.h>
>
> #define u64 uint64_t
>
> /*
>  * Compute *d = (a << s)
>  *
>  * Returns true if '*d' cannot hold the result or 'a << s' doesn't make sense.
>  * - 'a << s' causes bits to be lost when stored in d
>  * - 's' is garbage (eg negative) or so large that a << s is guarenteed to be 0
>  * - 'a' is negative
>  * - 'a << s' sets the sign bit, if any, in '*d'
>  * *d is not defined if false is returned.
>  */
> #define check_shift_overflow(a, s, d)                                          \
> 	({                                                                     \
> 		typeof(a) _a = a;                                              \
> 		typeof(s) _s = s;                                              \
> 		typeof(d) _d = d;                                              \
> 		u64 _a_full = _a;                                              \
> 		unsigned int _to_shift =                                       \
> 			_s >= 0 && _s < 8 * sizeof(*d) ? _s : 0;               \
>                                                                                \
> 		*_d = (_a_full << _to_shift);                                  \
>                                                                                \
> 		(_to_shift != _s || *_d < 0 || _a < 0 ||                       \
> 		 (*_d >> _to_shift) != a);                                     \
> 	})
>
> int main(int argc, const char *argv[])
> {
> 	int32_t s32;
> 	uint32_t u32;
>
> 	assert(check_shift_overflow(1, 0, &s32) == false && s32 == (1 << 0));
> 	assert(check_shift_overflow(1, 1, &s32) == false && s32 == (1 << 1));
> 	assert(check_shift_overflow(1, 30, &s32) == false && s32 == (1 << 30));
> 	assert(check_shift_overflow(1, 31, &s32) == true);
> 	assert(check_shift_overflow(1, 32, &s32) == true);
> 	assert(check_shift_overflow(-1, 1, &s32) == true);
> 	assert(check_shift_overflow(-1, 0, &s32) == true);
>
> 	assert(check_shift_overflow(1, 0, &u32) == false && u32 == (1 << 0));
> 	assert(check_shift_overflow(1, 1, &u32) == false && u32 == (1 << 1));
> 	assert(check_shift_overflow(1, 30, &u32) == false && u32 == (1 << 30));
> 	assert(check_shift_overflow(1, 31, &u32) == false && u32 == (1UL << 31));
> 	assert(check_shift_overflow(1, 32, &u32) == true);
> 	assert(check_shift_overflow(-1, 1, &u32) == true);
> 	assert(check_shift_overflow(-1, 0, &u32) == true);
>
> 	assert(check_shift_overflow(0xFFFFFFFF, 0, &u32) == false && u32 == (0xFFFFFFFFUL << 0));
> 	assert(check_shift_overflow(0xFFFFFFFF, 1, &u32) == true);
> 	assert(check_shift_overflow(0xFFFFFFFF, 0, &s32) == true);
> 	assert(check_shift_overflow(0xFFFFFFFF, 1, &s32) == true);
> }
>
> Thanks,
> Jason

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

[Rasmus Villemoes]

On 2018-06-27 20:22, Leon Romanovsky wrote:
> On Wed, Jun 27, 2018 at 12:10:12PM -0600, Jason Gunthorpe wrote:
>> On Wed, Jun 27, 2018 at 11:36:03AM +0200, Rasmus Villemoes wrote:
>>>    Well, the types you can check at compile-time, the values not, so you
>>>    still have to define the result, i.e. contents of *d, for negative
>>>    values (even if we decide that "overflow" should always be signalled in
>>>    that case).
>>
>> Why do a need to define a 'result' beyond whatever the not-undefined
>> behavior shift expression produces?

Well, perhaps you don't, it's just that the other check_*_overflow have
that behaviour (which they inherit from gcc's builtins), and it's a
nice-to-have. But I see that it's hard to come up with something
sensible in all the "doesn't make sense" cases. When writing the tests
for test_overflow.c, you can of course just omit the comparison to
the/an expected result in the overflow case.

>> /*
>>  * Compute *d = (a << s)
>>  *
>>  * Returns true if '*d' cannot hold the result or 'a << s' doesn't make sense.
>>  * - 'a << s' causes bits to be lost when stored in d
>>  * - 's' is garbage (eg negative) or so large that a << s is guarenteed to be 0
>>  * - 'a' is negative
>>  * - 'a << s' sets the sign bit, if any, in '*d'
>>  * *d is not defined if false is returned.
>>  */
>> #define check_shift_overflow(a, s, d)                                          \
>> 	({                                                                     \
>> 		typeof(a) _a = a;                                              \
>> 		typeof(s) _s = s;                                              \
>> 		typeof(d) _d = d;                                              \
>> 		u64 _a_full = _a;                                              \
>> 		unsigned int _to_shift =                                       \
>> 			_s >= 0 && _s < 8 * sizeof(*d) ? _s : 0;               \
>>                                                                                \
>> 		*_d = (_a_full << _to_shift);                                  \
>>                                                                                \
>> 		(_to_shift != _s || *_d < 0 || _a < 0 ||                       \
>> 		 (*_d >> _to_shift) != a);                                     \
>> 	})

That last a still needs to be _a. Other than that, I don't see anything
wrong with this version.

>> int main(int argc, const char *argv[])
>> {
>> 	int32_t s32;
>> 	uint32_t u32;
>>
>> 	assert(check_shift_overflow(1, 0, &s32) == false && s32 == (1 << 0));
[...]>> 	assert(check_shift_overflow(0xFFFFFFFF, 1, &s32) == true);

Please add these in some form to test_overflow.c, but do also include
cases where a and *d have different width, e.g. check_shift_overflow(1,
32, &s64) should be ok, while check_shift_overflow(65432, 0, &s16)
should not.

Rasmus

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

[Kees Cook]

On Wed, Jun 27, 2018 at 11:10 AM, Jason Gunthorpe <jgg@mellanox.com> wrote:
> Leon? Seems like agreement, Can you work with this version?
>
> #include <stdint.h>
> #include <stdbool.h>
> #include <assert.h>
>
> #define u64 uint64_t
>
> /*
>  * Compute *d = (a << s)
>  *
>  * Returns true if '*d' cannot hold the result or 'a << s' doesn't make sense.
>  * - 'a << s' causes bits to be lost when stored in d
>  * - 's' is garbage (eg negative) or so large that a << s is guarenteed to be 0
>  * - 'a' is negative
>  * - 'a << s' sets the sign bit, if any, in '*d'
>  * *d is not defined if false is returned.
>  */
> #define check_shift_overflow(a, s, d)                                          \
>         ({                                                                     \
>                 typeof(a) _a = a;                                              \
>                 typeof(s) _s = s;                                              \
>                 typeof(d) _d = d;                                              \
>                 u64 _a_full = _a;                                              \
>                 unsigned int _to_shift =                                       \
>                         _s >= 0 && _s < 8 * sizeof(*d) ? _s : 0;               \
>                                                                                \
>                 *_d = (_a_full << _to_shift);                                  \
>                                                                                \
>                 (_to_shift != _s || *_d < 0 || _a < 0 ||                       \
>                  (*_d >> _to_shift) != a);                                     \
>         })
>
> int main(int argc, const char *argv[])
> {
>         int32_t s32;
>         uint32_t u32;
>
>         assert(check_shift_overflow(1, 0, &s32) == false && s32 == (1 << 0));
>         assert(check_shift_overflow(1, 1, &s32) == false && s32 == (1 << 1));
>         assert(check_shift_overflow(1, 30, &s32) == false && s32 == (1 << 30));
>         assert(check_shift_overflow(1, 31, &s32) == true);
>         assert(check_shift_overflow(1, 32, &s32) == true);
>         assert(check_shift_overflow(-1, 1, &s32) == true);
>         assert(check_shift_overflow(-1, 0, &s32) == true);
>
>         assert(check_shift_overflow(1, 0, &u32) == false && u32 == (1 << 0));
>         assert(check_shift_overflow(1, 1, &u32) == false && u32 == (1 << 1));
>         assert(check_shift_overflow(1, 30, &u32) == false && u32 == (1 << 30));
>         assert(check_shift_overflow(1, 31, &u32) == false && u32 == (1UL << 31));
>         assert(check_shift_overflow(1, 32, &u32) == true);
>         assert(check_shift_overflow(-1, 1, &u32) == true);
>         assert(check_shift_overflow(-1, 0, &u32) == true);
>
>         assert(check_shift_overflow(0xFFFFFFFF, 0, &u32) == false && u32 == (0xFFFFFFFFUL << 0));
>         assert(check_shift_overflow(0xFFFFFFFF, 1, &u32) == true);
>         assert(check_shift_overflow(0xFFFFFFFF, 0, &s32) == true);
>         assert(check_shift_overflow(0xFFFFFFFF, 1, &s32) == true);
> }

Oh yes, please include these tests in lib/test_overflow.c too! Nice. :)

-Kees

-- 
Kees Cook
Pixel Security

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

[Peter Zijlstra]

On Tue, Jun 26, 2018 at 11:54:35AM -0600, Jason Gunthorpe wrote:

> What about more like this?
> 
>           check_shift_overflow(a, s, d) ({

Should that not be: check_shl_overflow() ? Just 'shift' lacks a
direction.

> 	      // Shift is always performed on the machine's largest unsigned
>               u64 _a = a;
> 	      typeof(s) _s = s;
>               typeof(d) _d = d;
> 
> 	      // Make s safe against UB
> 	      unsigned int _to_shift = _s >= 0 && _s < 8*sizeof(*d) : _s ? 0;

Should we not do a gcc-plugin or something that fixes that particular
UB? Shift acting all retarded like that is just annoying. I feel we
should eliminate UBs from the language where possible, like
-fno-strict-overflow mandates 2s complement.

>               *_d = (_a << _to_shift);
> 
> 	       // s is malformed
>               (_to_shift != _s ||

Not strictly an overflow though, just not expected behaviour.

> 	       // d is a signed type and became negative
> 	       *_d < 0 ||

Only a problem if it wasn't negative to start out with.

> 	       // a is a signed type and was negative
> 	       _a < 0 ||

Why would that be a problem? You can shift left negative values just
fine. The only problem is when you run out of sign bits.

> 	       // Not invertable means a was truncated during shifting
> 	       (*_d >> _to_shift) != a))
>           })

And I'm not exactly seeing the use case for this macro. What's the point
of a shift-left if you cannot truncate bits. I suppose it's in the name
_overflow, but still.

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

[Jason Gunthorpe]

On Wed, Aug 01, 2018 at 11:36:03AM +0200, Peter Zijlstra wrote:
> On Tue, Jun 26, 2018 at 11:54:35AM -0600, Jason Gunthorpe wrote:
> 
> > What about more like this?
> > 
> >           check_shift_overflow(a, s, d) ({
> 
> Should that not be: check_shl_overflow() ? Just 'shift' lacks a
> direction.

Yes, that makes sense.

> > 	      // Shift is always performed on the machine's largest unsigned
> >               u64 _a = a;
> > 	      typeof(s) _s = s;
> >               typeof(d) _d = d;
> > 
> > 	      // Make s safe against UB
> > 	      unsigned int _to_shift = _s >= 0 && _s < 8*sizeof(*d) : _s ? 0;
> 
> Should we not do a gcc-plugin or something that fixes that particular
> UB? Shift acting all retarded like that is just annoying. I feel we
> should eliminate UBs from the language where possible, like
> -fno-strict-overflow mandates 2s complement.

No idea, if someone does this they can remove the above overhead..

> >               *_d = (_a << _to_shift);
> > 
> > 	       // s is malformed
> >               (_to_shift != _s ||
> 
> Not strictly an overflow though, just not expected behaviour.

'overflow' here means the math didn't work, ie
   C = A << B
has a C that does not match A << B done on infinite precision. It is
not limited to checking overflow.

> > 	       // d is a signed type and became negative
> > 	       *_d < 0 ||
> 
> Only a problem if it wasn't negative to start out with.

> > 	       // a is a signed type and was negative
> > 	       _a < 0 ||
>
> Why would that be a problem? You can shift left negative values just
> fine. The only problem is when you run out of sign bits.

These are both a problem because of how the macro is setup, nobody had
an idea how to make this work with different types and allow for
negatives to work properly.

You could define this, but since there is no usecase..

> > 	       // Not invertable means a was truncated during shifting
> > 	       (*_d >> _to_shift) != a))
> >           })
> 
> And I'm not exactly seeing the use case for this macro. What's the point
> of a shift-left if you cannot truncate bits. I suppose it's in the name
> _overflow, but still.

It is basically a specialized case of check_mul_overflow where the
multiply is known to be a power of 2.

Jason

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

[Leon Romanovsky]

[-- Attachment #1: Type: text/plain, Size: 2242 bytes --]

On Mon, Jun 25, 2018 at 11:26:05AM +0200, Rasmus Villemoes wrote:
> On 24 June 2018 at 10:23, Leon Romanovsky <leon@kernel.org> wrote:
>
> > From: Leon Romanovsky <leonro@mellanox.com>
> >
> > Add shift_overflow() helper to help driver authors to ensure that
> > shift operand doesn't cause to overflow, which is very common pattern
> > for RDMA drivers.
> >
>
> Not a huge fan. The other _overflow functions have a different behaviour
> (in how they return the result and the overflow status) and are
> type-generic, and I think someone at some point will use such a
> generically-named helper for stuff other than size_t. At least the
> array_size and struct_size helpers have size in their name and are
> specifically about computing the size of something, and are designed to be
> used directly as arguments to allocators, where SIZE_MAX is a suitable
> sentinel. I can't see the other patches in this series, so I don't know how
> you plan on using it, but it should also be usable outside rdma.
>
> Aside: why does b have type size_t?
>
> Does __must_check really make sense for a function without side effects? It
> doesn't tell gcc to warn if the result is not used in a conditional, it
> just warns if the result is not used at all, which wouldn't realistically
> happen for a pure function.
>
> I'd much rather see a type-generic check_shift_overflow (we can agree to
> leave "left" out of the name) with semantics similar to the other
> check_*_overflow functions. Then, if a size_t-eating, SIZE_MAX-returning
> helper is more convenient for rdma, that should be easy to implement on top
> of that. It shouldn't really be that hard to do. Something like
>
> 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);
> }
>
> which should also handle shifts of signed types (though it allows << 0 for
> negative values; that's easy to also disallow). But the exact semantics
> should be documented via a bunch of tests (hint hint) exercising corner
> cases.

I'll respin.

Thanks for the feedback.

>
> Rasmus

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 801 bytes --]