Re: [RFC PATCH 08/10] linear-assignment.c: detect signed add/mul on GCC and Clang

[Jeff King <peff@peff.net>]

On Thu, Dec 09, 2021 at 08:19:25PM +0100, Ævar Arnfjörð Bjarmason wrote:

> diff --git a/linear-assignment.c b/linear-assignment.c
> index e9cec16132a..b6597b622c8 100644
> --- a/linear-assignment.c
> +++ b/linear-assignment.c
> @@ -10,7 +10,14 @@ static inline int cost_index(int *cost, int a, int b, int c)
>  {
>  	int r;
>  
> +#if defined(__GNUC__) || defined(__clang__)
> +	if (__builtin_mul_overflow(a, c, &r))
> +		die(_("integer overflow in cost[%d + %d * %c] multiplication"), b, a, c);
> +	if (__builtin_add_overflow(b, r, &r))
> +		die(_("integer overflow in cost[%d + ((%d * %d) = %d)] addition"), b, a, c, r);
> +#else
>  	r = b + a * c;
> +#endif

I think having an inline #if here is the wrong direction. We already
have signed_add_overflows() which you could use for the second check.
We haven't needed signed_mult_overflows() yet, but we could add one.

Those helpers don't use intrinsics yet. I think it would be reasonable
to have them do so when they're available. One of the big reasons we
haven't done so yet is that they're not generally in hot paths. We
generally use them while allocating, where the extra integer operations
and conditional aren't a big deal.

Here you depart from that and do the check on every index computation.
I'm not completely opposed to that approach, but I think a simpler
method (and what most spots have done so far) is to make sure the array
allocation itself is computed correctly, and then have code which
accesses it use an appropriate type to avoid overflow. In this case just
using size_t for the index computation would work, wouldn't it?

(Likewise, if you really want a negative value, then ssize_t should be
OK. It can't represent the full range of size_t, but if it would
overflow that implies the original allocation was consuming more than
half of the address space, which would have failed at the time of
allocation).

I do see that the following patch replaces this #if with similar helpers
from gnulib, which is better. And if we are going to go the route of
using intrinsics in our helpers, then it might be a good idea to use
gnulib's helpers to avoid portability pitfalls. But in that case we
should probably be converting over callers of the existing helpers (and
getting rid of those helpers).

IMHO it isn't really worth it, though, if we can solve this just by
switching to a more appropriate type here (and assuming there's not a
big performance benefit to the other helper call sites).

-Peff